Sorted Array to Balanced BST

Building a Tree Is Just Recursion in Reverse

Every tree problem you've seen so far starts with a tree and extracts information from it. This one goes the other direction — you start with data and construct a tree. The recursive thinking is identical: pick one element to be the root, then let recursion handle the rest.

Problem: Sorted Array to BST (LC 108)

Problem: Given an integer array \(nums\) sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than 1.

Input: \([1, 2, 3, 4, 5, 6, 7]\)

One valid output:

The Recursive Insight

A sorted array already tells you the in-order traversal of the BST. The question is: which element becomes the root?

If you pick the middle element, the left half becomes the left subtree and the right half becomes the right subtree. Both halves have roughly equal size, so the tree is balanced. Then you do the same thing recursively on each half.

This is divide-and-conquer — the same strategy as merge sort, but instead of splitting and merging, you're splitting and building.

The connection to binary search: The BST you construct IS the decision tree of binary search on this array. The root is the first element binary search checks. The left subtree contains elements binary search explores when the target is smaller. This isn't a coincidence — a BST encodes binary search as a data structure.

Picking the middle element as root divides the array into balanced halves

Full Trace

Input: \([1, 2, 3, 4, 5, 6, 7]\) (indices 0 through 6).

Call	leftBound	rightBound	midIndex	Node created	Left half	Right half
1	0	6	3	4	[0..2]	[4..6]
2	0	2	1	2	[0..0]	[2..2]
3	0	0	0	1	[0..-1] = null	[1..0] = null
4	2	2	2	3	[2..1] = null	[3..2] = null
5	4	6	5	6	[4..4]	[6..6]
6	4	4	4	5	[4..3] = null	[5..4] = null
7	6	6	6	7	[6..5] = null	[7..6] = null

Assembly (bottom-up): - Call 3 returns node 1 (no children). - Call 4 returns node 3 (no children). - Call 2 returns node 2, with left = node 1, right = node 3. - Call 6 returns node 5 (no children). - Call 7 returns node 7 (no children). - Call 5 returns node 6, with left = node 5, right = node 7. - Call 1 returns node 4, with left = node 2, right = node 6.

Result:

Manual verification: In-order traversal of this tree: \(1, 2, 3, 4, 5, 6, 7\). Matches the input. Heights: left subtree of root has height 1, right subtree has height 1. Balanced.

Why the Middle Element?

If you pick the first element as the root, the left subtree is empty and the right subtree has \(n-1\) elements. You get a skewed tree — a linked list, not a BST. Height \(= n - 1\) instead of \(\log n\).

If you pick the last element, same problem in the other direction.

The middle element guarantees each half has at most \(\lfloor n/2 \rfloor\) elements, so the tree height is \(O(\log n)\). For even-length arrays, you can pick either of the two middle elements — both produce valid balanced BSTs.

The Code

TreeNode* buildBST(vector<int>& nums, int leftBound, int rightBound) {
    if (leftBound > rightBound) return nullptr;

    int midIndex = leftBound + (rightBound - leftBound) / 2;
    TreeNode* node = new TreeNode(nums[midIndex]);
    node->left = buildBST(nums, leftBound, midIndex - 1);
    node->right = buildBST(nums, midIndex + 1, rightBound);
    return node;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return buildBST(nums, 0, nums.size() - 1);
}

Complexity: \(O(n)\) time (each element becomes exactly one node), \(O(\log n)\) space (recursion stack depth on a balanced tree).

The Recursion Tree IS the BST

Here's something worth staring at. Draw the recursion tree of buildBST — which calls happen, and in what order:

          buildBST(0,6) → creates 4
         /                        \
   buildBST(0,2) → creates 2    buildBST(4,6) → creates 6
    /          \                   /           \
 build(0,0)  build(2,2)       build(4,4)    build(6,6)
 → creates 1 → creates 3     → creates 5   → creates 7

The recursion tree has the exact same shape as the BST it builds. This always happens with divide-and-conquer construction — the structure of the algorithm mirrors the structure of the output.

Try It

Input: nums = [1, 2, 3, 4, 5, 6, 7]
Output (inorder): 1 2 3 4 5 6 7
Root value: 4

Predict before running: What tree does sortedArrayToBST produce for \([1, 2, 3]\)? Mid = index 1, value 2. Left half = [1], right half = [3]. Tree: root 2, left child 1, right child 3. Balanced, height 1.

Challenge: What if the input is a sorted linked list instead of an array? You can't index into the middle in \(O(1)\). How would you find the middle element? (Hint: slow/fast pointer technique from linked list problems.)

Edge Cases to Watch For

Empty array with unsigned arithmetic: nums.size() - 1 underflows to a huge value when nums is empty because size() returns an unsigned type. Cast to int first: (int)nums.size() - 1. Without this cast, the initial bounds are wrong and the recursion accesses out-of-bounds memory.

Problems

Problem	Link	Difficulty
LC 108 --- Convert Sorted Array to BST	leetcode.com/problems/convert-sorted-array-to-binary-search-tree	Easy
LC 109 --- Convert Sorted List to BST	leetcode.com/problems/convert-sorted-list-to-binary-search-tree	Medium
LC 1382 --- Balance a BST	leetcode.com/problems/balance-a-binary-search-tree	Medium
LC 654 — Maximum Binary Tree	leetcode.com/problems/maximum-binary-tree	Medium
LC 889 — Construct from Preorder and Postorder	leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal	Medium
LC 449 — Serialize and Deserialize BST	leetcode.com/problems/serialize-and-deserialize-bst	Medium

What's Next?

You can build trees. But one special kind of tree — the BST — has a structural invariant that unlocks sorted-order operations. Chapter 6 teaches you to exploit this invariant.