Convert Sorted Array to BST: A Step-by-Step Interview Walkthrough
- 2 days ago
- 9 min read
Convert Sorted Array to BST is a problem interviewers like because it tests whether you understand that structure emerges from constraints, not from clever code. The problem gives you two requirements — BST ordering and height balance — and the right algorithm falls out almost immediately if you reason about what those constraints mean together. The signal here is whether you can extract algorithmic structure from problem constraints rather than fighting them.
Building balanced search trees from sorted data underpins how databases bulk-load B-trees from sorted records (much faster than inserting one at a time), how interval trees and segment trees are constructed from sorted endpoints, how cache-oblivious data structures pick split points, and how skip lists choose their level distributions. Any time you have a sorted dataset and want O(log n) lookups afterward, this pattern is the foundation.
Problem Statement
Given an integer array nums sorted in ascending order, convert it into a height-balanced binary search tree.
A height-balanced BST is one in which the depth of the two subtrees of every node never differs by more than one.
Return the root of the constructed BST.
Example:
nums = [-10, -3, 0, 5, 9]
one valid output:
0
/ \
-10 5
\ \
-3 91. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.
Input: a sorted array of integers (may be empty).
Output: the root of a height-balanced BST containing those integers.
Details to clarify:
Is the input strictly sorted, or can it have duplicates? Usually allowed to have duplicates — they go into the tree as-is.
Is there a unique correct answer? No — multiple valid balanced BSTs may exist. Any one is acceptable.
What does "height-balanced" mean precisely? At every node, the depths of the left and right subtrees differ by at most 1.
Can the array be empty? Yes — return null.
Do we need to preserve the order of duplicates? Not generally — BSTs care about values, not original positions.
The thing to flag is the combination of sorted input and balanced output. Each constraint on its own would suggest different algorithms; together they pin down the solution almost completely. Reading both carefully is the difference between a clean algorithm and an overcomplicated one.
2. Identify the Category of the Question
A few signals jump out:
The input has structure (it's sorted).
The output is a tree, built recursively.
Each node we create defines a subproblem on a contiguous slice of the input.
The same algorithm applies at every level.
That combination — recursive construction, contiguous-slice subproblems, self-similar structure — points to divide and conquer. Same family as Merge Sort and Quick Sort: pick a splitter, recurse on both halves, combine. The twist here is that "combining" is essentially free — we just attach the recursive results as the left and right children of the current node.
3. Brute Force Solution
As always, we start with the most naive approach. The most direct way to build a BST is to insert values one at a time:
TreeNode root = null;
for (int num : nums) {
root = insert(root, num);
}This builds a valid BST, but here's the problem: the input is sorted. Inserting sorted values into a BST produces a degenerate tree — every new value is larger than the current root, so it always goes to the right. The result is essentially a linked list with depth n, not a balanced tree of depth log n. That violates the height-balance requirement and gives us O(n²) total construction time, too.
The brute force teaches us something important: balance won't happen by accident. If we let the insertion order drive the structure, sorted input is the worst possible case. We have to design the algorithm so that balance is a consequence of how we build the tree.
4. Brainstorm More Solutions
Step 1: What would a balanced tree even look like?
Before designing an algorithm, let's think about what we're trying to produce. A height-balanced BST on n nodes has depth roughly log₂(n). For n = 7, the tree looks like:
4
/ \
2 6
/ \ / \
1 3 5 7Notice anything about that picture? The root is the middle element. Its left subtree contains all values smaller than the root; its right subtree contains all values larger. And the left and right subtrees are themselves balanced BSTs on roughly half the elements each.
That observation alone is most of the solution. We're not constructing a tree from scratch — the shape of the balanced tree is already determined by the requirements, and the contents are determined by the sorted order. We just have to read out the right values for each position.
Step 2: Why does picking the middle work?
Let's check this more carefully. If we pick the middle element of a sorted array as the root, then:
BST ordering is automatic. Every value to the left of the middle in the array is smaller than the middle (because the array is sorted). Every value to the right is larger. So putting the left half into the left subtree and the right half into the right subtree satisfies BST ordering by construction.
Balance is automatic, too. If we always pick the middle, the left half has ⌊n/2⌋ elements and the right half has ⌈n/2⌉ - 1 elements — at most one off from each other. If we apply the same rule recursively to each half, the depths grow at the same rate. The result is balanced by construction.
So the algorithm is: pick the middle, make it the root, recurse on the left half for the left subtree, recurse on the right half for the right subtree. That's it.
Step 3: Write down the recurrence
Let build(left, right) return the root of a balanced BST built from nums[left..right] (inclusive).
Base case: if left > right, the range is empty — return null.
Recursive case:
Pick the middle index: mid = left + (right - left) / 2.
Create a new node with nums[mid] as its value.
Recursively build the left subtree from nums[left..mid-1].
Recursively build the right subtree from nums[mid+1..right].
Return the new node.
Notice that we pass indices rather than slicing the array. Slicing copies data, which would push space complexity up to O(n log n). Indices are O(1) per call and let us reuse the original array.
A small detail worth pausing on: the midpoint formula. The intuitive way to compute it is (left + right) / 2, but that can overflow if left + right exceeds the integer limit. The safe form is left + (right - left) / 2, which is mathematically equivalent but never overflows because right - left is bounded by the array length. This isn't usually a concern for interview-sized inputs, but it's a habit worth showing — interviewers notice.
Step 4: Left-middle or right-middle for even lengths?
A subtle point: when the range has an even number of elements, there are two "middle" elements. For [1, 2, 3, 4], the middle is either index 1 (value 2) or index 2 (value 3). Which one should we pick?
Both work, and both produce valid height-balanced BSTs — they just produce different valid trees. The integer division (left + right) / 2 naturally picks the left middle, which results in slightly heavier right subtrees. If we computed (left + right + 1) / 2, we'd pick the right middle, with slightly heavier left subtrees. The problem explicitly allows any valid answer, so this is a stylistic choice with no correctness implications.
I'd pick whichever feels natural and not worry about it. If an interviewer asks, the answer is: "Both work; the choice affects which valid tree we produce, but balance is preserved either way."
Step 5: Complexity
Each element of the array becomes exactly one node in the tree, and each node is created by one O(1) call to build (excluding the recursive calls). So total work is O(n).
Space comes in two flavors:
Output space: the tree itself contains n nodes — O(n). This is required by the problem.
Auxiliary space: the recursion stack. Because the tree is balanced, the recursion depth is O(log n), so the stack uses O(log n) space.
So O(n) time and O(log n) auxiliary space.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Incremental BST insertion (sorted input) | O(n²) | O(n) tree depth | Never — produces a degenerate, unbalanced tree |
Incremental BST with rebalancing (AVL-style) | O(n log n) | O(log n) | Overkill for sorted input; useful only if the input weren't sorted |
Recursive midpoint construction | O(n) | O(log n) | My default answer — clean, balanced, optimal |
The midpoint approach is the only one that exploits the sorted input. The other approaches either ignore it (and pay for that ignorance) or compensate with extra machinery that isn't needed.
6. Pseudocode
sortedArrayToBST(nums):
return build(nums, 0, nums.length - 1)
build(nums, left, right):
if left > right:
return null
mid = left + (right - left) / 2
node = new TreeNode(nums[mid])
node.left = build(nums, left, mid - 1)
node.right = build(nums, mid + 1, right)
return nodeThat's the entire algorithm. Five lines of recursive logic plus a one-line wrapper.
7. Edge Cases
Things to verify before claiming we're done:
Empty array → build(0, -1) hits the base case immediately, returns null. ✓
Single-element array → build(0, 0) creates a node, both recursive calls return null, returns a leaf. ✓
Two elements → build(0, 1) picks mid = 0, creates a node from nums[0], left is null, right is a single-node subtree from nums[1]. Depths differ by 1 — still balanced. ✓
Odd length (e.g., 5) → perfectly balanced tree.
Even length (e.g., 6) → tree balanced within tolerance of 1.
Duplicate values → values are inserted positionally; the BST property is preserved as long as duplicates are handled consistently (e.g., always going right).
The left > right base case handles every degenerate range without special logic. That's the sign of clean recursion.
8. Full Code
public class ConvertSortedArrayToBST {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return build(nums, 0, nums.length - 1);
}
private static TreeNode build(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// Use this form instead of (left + right) / 2 to avoid overflow on large arrays
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums, left, mid - 1);
node.right = build(nums, mid + 1, right);
return node;
}
}9. Test the Code
// Standard case
int[] nums = {-10, -3, 0, 5, 9};
TreeNode root = sortedArrayToBST(nums);
// One valid output:
// 0
// / \
// -10 5
// \ \
// -3 9
// Empty array
System.out.println(sortedArrayToBST(new int[]{})); // null
// Single element
TreeNode single = sortedArrayToBST(new int[]{42});
System.out.println(single.val); // 42
// Two elements
TreeNode two = sortedArrayToBST(new int[]{1, 2});
// mid = 0, root = 1, right child = 2
// Even length
int[] even = {1, 2, 3, 4, 5, 6};
TreeNode evenRoot = sortedArrayToBST(even);
// One valid output: root = 3, balanced within depth tolerance of 1
// Larger array — verify balance, not exact structure
int[] large = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
TreeNode largeRoot = sortedArrayToBST(large);
// Should be a perfectly balanced tree with root = 8These hit the meaningful cases: a standard balanced output, the empty case, a single node, two-element handling, even-length tiebreaking, and a larger array to verify the balance property holds at scale.
10. Key Lessons
When a problem gives you a sorted input, that ordering is itself algorithmic information. Sorted inputs let you split in the middle and get useful structural guarantees on both halves for free. Don't ignore the sort.
Balance in a tree is something you design, not something you fix. The cleanest algorithms enforce balance through how the tree is constructed, not through post-hoc rebalancing.
When constructing a tree from an array, pass indices rather than slicing. Slicing creates O(n)-per-level copies and bloats space complexity. Index-based recursion is O(1) per call.
The integer overflow trick — mid = left + (right - left) / 2 instead of (left + right) / 2 — is worth using by default. It costs nothing and shows attention to detail.
Divide and conquer on sorted input is the same shape as building a balanced search tree from scratch, and the same shape as binary search itself. Recognize the family — pick a splitter, recurse on each side — and you'll see it in dozens of problems.
The thing that makes Convert Sorted Array to BST click isn't the algorithm — picking the middle is obvious in hindsight. It's the recognition that the constraints (sorted input + balanced output) already determine the algorithm. Once you trust that constraints encode the solution, you stop fighting them and start reading them. Every tree-construction problem starts to feel less like invention and more like translation.
Good Luck and Happy Coding!
Comments