Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree: build a height-balanced binary search tree from an array sorted in ascending order.
- 1 <= nums.length <= 10⁴
- -10⁴ <= nums[i] <= 10⁴
- nums is sorted in a strictly increasing order
Intuition
Choosing the middle element as the root splits the remaining values into two halves of nearly equal size, and every value on the left is smaller while every value on the right is larger — which is exactly the BST property. Recursing on each half applies the same reasoning one level down, so the tree is balanced by construction rather than by any rebalancing step.
Divide and conquer on a sorted array shows up whenever the midpoint carries structural meaning — as a root, a pivot, or a boundary. The signal here is that sortedness plus balance are both required, and one choice of split delivers both.
Approach
Before reading on: explain why the middle element must be the root if the tree is to stay balanced, and what shape results from always picking the first element instead. Then decide whether to pass slices or index bounds.
The midpoint choice does two jobs at once
Picking mid as the root satisfies the search-tree ordering for free, because the array is sorted: everything at a lower index is smaller and everything at a higher index is larger. It simultaneously satisfies the balance requirement, because the two remaining subarrays differ in length by at most one. No other choice of root achieves both — selecting the first element, for instance, still yields a valid BST but degenerates into a right-leaning chain of height n.
Recursion on index ranges, not slices
Pass lo and hi bounds rather than slicing the array. Slicing copies the subarray at every call, adding O(n log n) total copying work and O(n) extra memory for no gain. With index bounds the recursion touches each element once and the only extra space is the call stack. The base case is lo > hi, an empty range, which returns None — that is what terminates the recursion and creates the leaves' null children.
Why the answer is not unique, and what balanced means
With an even-length range there are two valid midpoints, and both produce height-balanced trees, so many correct answers exist — LeetCode accepts any of them. Height-balanced means every node's two subtrees differ in height by at most one. The midpoint split guarantees this inductively: if both halves are balanced and their sizes differ by at most one, their heights differ by at most one too. The resulting height is ⌈log₂(n + 1)⌉, the minimum possible for n nodes. Time is O(n), space O(log n) for the stack.
Solution & live demo
Common pitfalls
Slicing the array at every call
node.left = self.sortedArrayToBST(nums[:mid]) node.right = self.sortedArrayToBST(nums[mid + 1:])
node.left = build(lo, mid - 1) node.right = build(mid + 1, hi)
Each slice copies its subarray, adding O(n log n) work and O(n) memory overall. Index bounds describe the same ranges without duplicating any data.
Choosing the first element as the root
node = TreeNode(nums[lo]) node.right = build(lo + 1, hi)
mid = (lo + hi) // 2 node = TreeNode(nums[mid])
The result is still a valid BST but degenerates into a chain of height n, so lookups become linear. The balance requirement is precisely what the midpoint choice satisfies.
Off-by-one in the recursive bounds
node.left = build(lo, mid) node.right = build(mid, hi)
node.left = build(lo, mid - 1) node.right = build(mid + 1, hi)
Including mid in either half means the range never shrinks past it, so the same element is inserted forever and the recursion overflows the stack.
Edge cases
lo > hi immediately, so None is returned as the whole tree.
Becomes a leaf whose two recursive calls both return None.
One becomes the root and the other a single child; height 2 is balanced.
Either midpoint is acceptable; the shape differs but balance holds.
Only the ordering matters, so the actual values are irrelevant to the structure.