Why it works
- Everything left of the middle is smaller and everything right of it is larger, so the middle as the root with the halves below it is a search tree, and the same holds inside each half.
- The two halves differ in size by at most one value, so their trees differ in height by at most one: the whole tree is balanced.
- With an even count either middle works; rounding down just puts the extra value on the right, as with -7 and -2.
Complexity
Time O(n): each value becomes a node once, and a call does O(1) work besides its two calls. Memory O(log n) besides the tree: the call stack is as deep as the balanced tree is tall.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗