Sorted Array to Balanced BST

Sorted Array to Balanced BST turns a sorted list into a binary search tree that is as short as possible. The whole trick is one observation: a sorted array is already the inorder reading of a BST, so the only real decision is which element to make the root at each step.

The slow way first

You could insert the values one by one into an empty BST. But the array is already sorted, so each insert lands as far right as possible and the tree degenerates into a straight line of 5 nodes — height O(n), no better than the original array. Inserting in sorted order is the worst case for a plain BST.

The question to ask: what single value, placed at the root, splits the work evenly? If we put the middle value at the root, then exactly half the remaining values go left and half go right — and the BST ordering is automatically satisfied, because everything before the middle is smaller and everything after is larger.

The idea: the middle is always the root

Pick the middle element of the current range as the subtree root. Everything to its left is smaller, so it becomes the left subtree; everything to its right is larger, so it becomes the right subtree. Then solve each half the same way — recursively. Halving the range at every level is exactly what binary search does, which is why the resulting height is O(log n).

The key insight: because the array is sorted, choosing the middle gives a root whose left half is all smaller and right half is all larger — the BST property holds for free, and the even split keeps the tree balanced.

Walk through it

Step through the animation with nums = [2, 5, 11, 14, 20]. The mid pointer marks the chosen root for each range, and the tree on the right grows one node at a time. The middle of the whole array, 11, becomes the root. The left half [2, 5] builds into 5 with 2 hanging beneath it; the right half [14, 20] builds into 20 with 14 beneath it. Five values, height three — the shortest tree possible.

Pseudocode

build(nums):
    if nums is empty:
        return None                       # nothing to build -> empty subtree
    mid = middle index of nums
    root = a new node holding nums[mid]
    root.left  = build(values left of mid)    # smaller values
    root.right = build(values right of mid)   # larger values
    return root

The Python solution

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

• The base case: an empty slice returns None, which is the empty subtree that stops the recursion.
• mid = len(nums) // 2 is the middle index of the current slice — the value that splits it evenly.
• root = TreeNode(nums[mid]) makes that middle value the root of this subtree.
• nums[:mid] is everything before the middle (all smaller), so it becomes the left subtree.
• nums[mid + 1:] is everything after the middle (all larger), so it becomes the right subtree.
• Each call returns the subtree root it just built, so the parent can link it as a child.

Complexity

Each value becomes exactly one node, but slicing nums[:mid] and nums[mid + 1:] copies sub-arrays at every level, which costs O(n log n) overall. Passing index bounds (lo/hi) instead of slicing drops the copies and brings the time to a clean O(n) without changing the idea. Space is O(n) for the tree; the recursion only goes O(log n) deep because the tree is balanced.

When this pattern shows up

Practice