Convert Sorted Array to BST: Divide and Conquer

May 13, 20266 min read

leetcodeproblemeasytreesbinary-search

You are 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 one.

This is LeetCode 108: Convert Sorted Array to Binary Search Tree, and it is one of the cleanest examples of divide and conquer on trees. The solution is short, but the intuition behind it reveals a pattern that shows up in many other problems.

The middle element (0) becomes the root. The left half [-10, -3] builds the left subtree. The right half [5, 9] builds the right subtree.

Why sorted order makes this possible

A binary search tree has a rule: every node's left subtree contains only smaller values, and every node's right subtree contains only larger values. If the input array is already sorted, you know exactly which elements belong on the left side and which belong on the right side of any chosen root.

The question is: which element should be the root? If you pick a value too far to the left, the right subtree ends up much deeper than the left. If you pick too far to the right, the opposite happens. To keep the tree balanced, you pick the middle element.

That single insight drives the entire solution.

The approach

Pick the middle element of the current array (or subarray) as the root.
Recursively build the left subtree from all elements to the left of the middle.
Recursively build the right subtree from all elements to the right of the middle.
Base case: if the array is empty, return None.

Because you always split roughly in half, the resulting tree is height-balanced. The left half has floor(n/2) elements and the right half has the rest. The depth difference between any two subtrees is at most 1.

This is the same divide-and-conquer pattern as binary search. In binary search, you pick the middle to decide which half to search. Here, you pick the middle to decide which element becomes the root, then you build both halves.

Practice divide and conquer tree problems

Python solution

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid + 1:])
    return root

Walkthrough

Let's trace through nums = [-10, -3, 0, 5, 9] step by step.

Step 1: Call with [-10, -3, 0, 5, 9]. mid = 2, so nums[2] = 0 becomes the root.

Pick the middle element of the full array. 0 is at index 2. It becomes the root of the BST.

Step 2: Call with [-10, -3]. mid = 1, so -3 becomes the left child of 0.

Left subarray is [-10, -3]. len is 2, mid = 1, so -3 becomes the left child of the root. Recurse on [-10] for its left subtree.

Step 3: Call with [-10]. Only one element, so -10 is a leaf.

Subarray has one element. -10 becomes a leaf node, the left child of -3. Both its left and right subarrays are empty.

Step 4: Call with [5, 9]. mid = 1, so 9 becomes the right child of 0.

Right subarray is [5, 9]. len is 2, mid = 1, so 9 becomes the right child of the root. Recurse on [5] for its left subtree.

Step 5: Call with [5]. Only one element, so 5 is a leaf.

Subarray has one element. 5 becomes a leaf node, the left child of 9.

Step 6: All recursion complete. The height-balanced BST is built.

Every node's left and right subtrees differ in height by at most 1. The BST property holds: left values are smaller, right values are larger.

Here is the full trace:

sorted_array_to_bst([-10, -3, 0, 5, 9]): mid = 2, root = 0. Left subarray: [-10, -3]. Right subarray: [5, 9].
sorted_array_to_bst([-10, -3]): mid = 1, root = -3. Left subarray: [-10]. Right subarray: [].
sorted_array_to_bst([-10]): mid = 0, root = -10. Both subarrays are empty. Returns leaf node -10.
sorted_array_to_bst([]): returns None. (Right child of -3 is None.)
sorted_array_to_bst([5, 9]): mid = 1, root = 9. Left subarray: [5]. Right subarray: [].
sorted_array_to_bst([5]): mid = 0, root = 5. Both subarrays are empty. Returns leaf node 5.
sorted_array_to_bst([]): returns None. (Right child of 9 is None.)

The final tree has 0 at the root, -3 and 9 as its children, with -10 and 5 as leaves. Every subtree is balanced.

The problem says "return any valid height-balanced BST." Multiple correct answers exist because you can choose either the left-middle or right-middle element when the subarray has even length. The solution above always picks the left-middle (len(nums) // 2), which is the convention LeetCode expects.

Complexity analysis

Metric	Value
Time	O(n)
Space	O(log n)

Time is O(n). Every element in the array is visited exactly once to create its corresponding tree node. The slicing creates copies, but across all levels of recursion the total work is still O(n).

Space is O(log n) for the call stack. Because you always split the array in half, the recursion depth is log n. The output tree itself takes O(n) space, but that is the required output, not auxiliary space.

If you want to avoid the overhead of array slicing, you can pass indices instead:

def sorted_array_to_bst(nums):
    def helper(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = helper(left, mid - 1)
        root.right = helper(mid + 1, right)
        return root

    return helper(0, len(nums) - 1)

This version uses O(log n) space with no extra allocations beyond the call stack.

Drill this pattern with spaced repetition

The building blocks

This problem is built on two fundamental building blocks.

Middle-element recursion. The core technique is selecting the middle element as the root and recursing on both halves. This is the same split-in-half logic that powers binary search, merge sort, and many other divide-and-conquer algorithms. Whenever you see a sorted input and need to build a balanced structure, picking the middle is almost always the right move.

Balanced tree construction. Building a tree by choosing the middle ensures that no subtree is much deeper than any other. This property (height balance) is what makes BST operations efficient at O(log n). Understanding why middle selection produces balance helps with problems involving AVL trees, segment trees, and any scenario where you need to construct a balanced hierarchy from sorted data.

# Middle-element recursion skeleton:
def build(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    node = TreeNode(nums[mid])
    node.left = build(nums[:mid])
    node.right = build(nums[mid + 1:])
    return node

These building blocks appear together in problems like Construct BST from Preorder, Convert Sorted List to BST, and any problem where you need to build a balanced tree from sequential data.

Edge cases to watch for

Empty array: return None. The base case if not nums handles this.
Single element: returns a single node with no children. mid = 0, left slice is empty, right slice is empty.
Two elements: [1, 2] produces root = 2 with left child 1. Or if you use the index-based approach with (0 + 1) // 2 = 0, root = 1 with right child 2. Both are valid height-balanced BSTs.
Even vs odd length: with odd length, the middle element is unique. With even length, you can pick either of the two middle elements. The len(nums) // 2 convention picks the right-center element for even-length arrays, which is what LeetCode expects.

From understanding to recall

You just traced through the entire recursion and saw how picking the middle element at every level produces a balanced BST. The logic is clean: split in half, make the middle the root, recurse on both sides. It all clicks right now.

But will you remember the details in two weeks? Will you remember that the base case checks for an empty array (not a null node, since you are building the tree from scratch)? Will you remember that mid = len(nums) // 2 gives you the right-center for even-length arrays? These small details are easy to mix up under pressure.

Spaced repetition locks them in. You practice typing this solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the middle selection, the slice boundaries, and the recursive calls. After a few reps, the pattern becomes automatic, and you can adapt it to harder problems like Convert Sorted List to BST without hesitation.

Validate Binary Search Tree - Tests whether a tree satisfies the BST property that this problem constructs, using range checking or inorder traversal
Maximum Depth of Binary Tree - The simplest tree recursion problem, a great warm-up before tackling tree construction

Try CodeBricks free