Convert Sorted Array to Binary Search Tree
Understanding the Problem
We're given a sorted array and need to build a binary search tree (BST) from it that's also height-balanced. The BST property means every node's left subtree contains only smaller values and the right subtree contains only larger values. Height-balanced means that at every node, the left and right subtree heights differ by at most 1.
A sorted array is the in-order traversal of the BST we want to build. To make the tree height-balanced, we want roughly equal numbers of nodes on the left and right of each subtree. That points to picking the middle element as the root, then recursing on the left half for the left subtree and the right half for the right subtree. This is a divide and conquer pattern.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, we can build the tree in O(n). Each element becomes exactly one node, so O(n) is optimal.-10^4 <= nums[i] <= 10^4→ Node values are small integers. No overflow concerns.nums is sorted in strictly increasing order→ No duplicates. Everything left of any chosen root is strictly smaller and everything right of it is strictly larger, so the BST property needs no tie handling.
Approach 1: Divide and Conquer (Optimal)
Intuition
A sorted array is the in-order traversal of a BST, and to make the BST height-balanced, each subtree needs roughly the same number of nodes on the left and right. The middle element achieves that.
If we pick the middle element as the root, all elements before it (the left half) form the left subtree, and all elements after it (the right half) form the right subtree. Both halves differ in size by at most 1. For each half, we apply the same logic: pick its middle element as the root of that subtree, and recurse.
This is divide and conquer: split the array at the middle, build each half recursively, and combine by making the middle element the parent of the two subtree roots.
Two invariants hold at every recursive call. BST property: the array is sorted, so every element in nums[left..mid-1] is smaller than nums[mid] and every element in nums[mid+1..right] is larger. Each node's left subtree contains only smaller values and its right subtree only larger ones.
Balance: the two halves differ in size by at most 1, and this holds at every level of recursion, so the subtree heights at any node differ by at most 1. The resulting tree's height is ceil(log2(n+1)), the minimum possible. The tree is height-balanced by construction.
Algorithm
- Define a recursive helper function that takes the left and right bounds of the current subarray.
- Base case: if left > right, return null (empty subarray, no node to create).
- Find the middle index: mid = left + (right - left) / 2.
- Create a new tree node with the value at nums[mid].
- Recursively build the left subtree from nums[left..mid-1].
- Recursively build the right subtree from nums[mid+1..right].
- Return the current node.
Example Walkthrough
Trace nums = [-10, -3, 0, 5, 9]. The array view shows the range each recursive call covers and the middle index it picks; the tree view below it shows the node each call creates.
Code
- Time Complexity: O(n). We visit each element exactly once and create one tree node per element. Each node creation is O(1) work.
- Space Complexity: O(log n). The recursion stack depth equals the height of the balanced tree. If you count the output tree, it's O(n), but the extra space for the algorithm itself is O(log n).
O(n) time is optimal because the output tree has n nodes. The remaining variation builds the same tree without recursion.
Approach 2: Iterative Using a Stack
Intuition
The same construction works without recursion. An explicit stack replaces the call stack: instead of relying on the runtime to track which subarray ranges still need processing, we manage a stack of "tasks" ourselves.
Each task on the stack stores: the parent node, which child (left or right) this task should attach to, and the subarray bounds (left, right). We process tasks the same way the recursive version does: find the middle, create a node, attach it to the parent, then push two new tasks for the left and right halves. Pushing the right half's task before the left half's means the left task sits on top of the stack and is popped first, so nodes are created in the same order as the recursive version.
Algorithm
- Create the root node using the middle element of the full array: mid = (n - 1) / 2, the same index the recursive version picks.
- Push two tasks onto a stack: first one for the right half (to become the root's right child), then one for the left half (to become the root's left child).
- While the stack is not empty, pop a task.
- If the subarray is empty (left > right), skip it.
- Otherwise, find the middle element, create a node, and attach it to the parent on the recorded side.
- Push two new tasks for the right and left halves of the current subarray, right first.
- When the stack is empty, every range has been processed. Return the root.
Example Walkthrough
The same input traced through the stack version. Each step shows the task popped from the stack, the range it covers, and the node it creates; tasks with an empty range are popped and skipped. The nodes appear in the same order as in the recursive version because the left task is always pushed last.
Code
- Time Complexity: O(n). Same as the recursive approach. Each element is processed exactly once.
- Space Complexity: O(log n). Popping a task at one level pushes two tasks one level deeper, so the stack holds at most a constant number of pending tasks per level of the tree being built. The tree's height is O(log n), so the stack never exceeds O(log n) entries.