The problem
Given a sorted (ascending) array, build a height-balanced binary search tree from it.
Stuck? Reveal hints one at a time
How to approach it
- 1build(lo, hi): if lo > hi, return null.
- 2mid = (lo + hi) >> 1; make a node from nums[mid].
- 3node.left = build(lo, mid − 1); node.right = build(mid + 1, hi).
- 4Return build(0, n − 1).
Key insight
Halving the array at every level bounds the height at ⌈log₂ n⌉ — balance comes from the construction, no rotations needed.
The solution
Watch out for
- Slicing arrays per call (nums[:mid]) costs O(n log n) total — pass indices instead.
- Either midpoint (lower or upper) yields a valid balanced tree; tests accept any.