Convert Sorted Array to Binary Search Tree
Last Updated: March 29, 2026
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.
Here's the key insight: because the array is already sorted, it's essentially an in-order traversal of the BST we want to build. And to make the tree height-balanced, we want roughly equal numbers of nodes on the left and right of each subtree. That points directly 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 classic divide and conquer pattern.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, O(n^2) works fine, but 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. The sorted order gives us the in-order traversal for free.
Approach 1: Brute Force (Insertion One by One)
Intuition
The simplest approach that comes to mind: just insert each element from the sorted array into a BST one at a time, the way you would normally build a BST. Start with an empty tree, and for each element, walk down the tree to find the correct position and insert it.
But here's the problem. If we insert elements in sorted order (1, 2, 3, 4, 5...), every new element is larger than the previous one, so it always goes to the right. We end up with a completely right-skewed tree, which is the opposite of balanced.
To make this work, we'd need to insert elements in a specific order that produces a balanced tree. What order? The middle element first, then the middles of each half, and so on. But once we figure out that order, we've basically arrived at the divide and conquer approach anyway. So the naive insertion approach either gives us an unbalanced tree or leads us to the optimal approach.
Algorithm
- Take the sorted array and insert elements one by one into an initially empty BST.
- For each element, start at the root and compare with each node.
- If the element is smaller, go left. If larger, go right.
- When you reach a null position, insert the new node there.
- After all insertions, the tree is a valid BST but likely not balanced.
Example Walkthrough
Input:
Inserting in sorted order produces a right-skewed BST:
Code
- Time Complexity: O(n^2). Each insertion walks down the tree. For sorted input, the tree becomes right-skewed, so the i-th insertion takes O(i) time. Total: 1 + 2 + ... + n = O(n^2).
- Space Complexity: O(n). We create n tree nodes. The recursion stack depth is O(n) in the worst case (skewed tree).
This approach doesn't even produce a balanced tree from sorted input. What if we picked the right root upfront, knowing that the middle element creates the most balanced split?
Approach 2: Divide and Conquer (Optimal)
Intuition
Here's the observation that changes everything. A sorted array is the in-order traversal of a BST. And to make the BST height-balanced, we want each subtree to have roughly the same number of nodes on the left and right. What element achieves that? The middle element.
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. Now, 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 in its purest form. We divide the array in half, conquer each half recursively, and combine by making the middle element the parent of the two subtree roots.
The correctness comes from two properties working together. First, because the array is sorted and we always pick elements to the left of mid for the left subtree and elements to the right for the right subtree, the BST property is automatically maintained. Every left subtree node has a smaller value than its parent, and every right subtree node has a larger value.
Second, by always picking the middle element, we ensure the left and right halves differ in size by at most 1 at every level of recursion. This means the resulting tree's height is ceil(log2(n+1)), which is as short as 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
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).
This is already optimal at O(n), but what if an interviewer asks for an iterative version to avoid recursion?
Approach 3: Iterative Using a Stack
Intuition
The recursive divide and conquer is clean and optimal, but some interviewers might ask for an iterative version. We can simulate the recursion using an explicit stack. Instead of relying on the call stack 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.
Algorithm
- Create the root node using the middle element of the full array.
- Push two tasks onto a stack: one for the left half (to become the root's left child) and one for the right half (to become the root's right 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.
- Push two new tasks for the left and right halves of the current subarray.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Same as the recursive approach. Each element is processed exactly once.
- Space Complexity: O(log n). The explicit stack holds at most O(log n) tasks at any time, matching the height of the balanced tree being built.