Build a balanced BST from sorted input

48 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You have the sorted list [−10, −3, 0, 5, 9] and must build a binary search tree from it. The lazy way is to insert the values one by one: −10 becomes the root, −3 goes to its right, 0 to the right of that, and so on. You get a tree that is really a chain leaning to the right, five levels deep. Searching it costs as much as scanning the list. A good BST is short and bushy, with the levels filled from the top, so that a search takes about log₂ n steps.

By hand, with the list in front of you, the right move is obvious: put the middle value on top so that half the values go left and half go right. Then do the same to each half.

Build the structure, one piece at a time

Piece one: a slice, described by two indices [lo, hi] into the sorted list. The whole list is [0, 4]. An empty slice (lo > hi) builds nothing.

Piece two: the middle. For a slice take m = (lo + hi) / 2 rounded down. The value at m becomes the root of this slice's subtree.

Piece three: recurse. The left child is built from [lo, m − 1] and the right child from [m + 1, hi]. Because the list is sorted, everything in the left slice is smaller than the root value and everything in the right slice is larger, so the BST rule is automatic.

The tree: 0 on top; −10 and 5 below; −3 under −10 on the right; 9 under 5 on the right. Three levels for five values instead of five.

Why it is correct

Two things to show. It is a BST: at every node, the left subtree was built from values before the root in the sorted list, so all smaller, and the right subtree from values after it, so all larger. It is balanced: a slice of s values splits into slices of sizes

⌊(s − 1)/2⌋ and ⌈(s − 1)/2⌉, which differ by at most 1

Two subtrees whose sizes differ by at most one, both built the same way, have heights that differ by at most one. The argument repeats inside each subtree, so every node is height-balanced, and the overall height is about log₂ n.

Why it is fast

Every value is placed exactly once, with constant work to compute the middle and the two slices: O(n) time. The recursion depth is the height, O(log n). Inserting one by one into an empty BST would have cost O(n log n) at best and O(n²) for already-sorted input. If the input is a sorted linked list rather than an array, you cannot index the middle, so either copy to an array first (O(n) extra memory) or build inorder while walking the list with a pointer that advances once per node, which is also O(n).

How to recognise it in an interview

"Sorted array to a height-balanced BST", "sorted linked list to BST", "rebalance this BST". Say: "The middle element becomes the root and I recurse on each half; the sorted order guarantees the BST rule and halving guarantees balance." Convert Sorted Array to Binary Search Tree is this exactly. Convert Sorted List to Binary Search Tree is the same with the list-walking trick. Balance a Binary Search Tree is two patterns joined: read the existing tree inorder into a sorted array, then rebuild it with this one.

02The idea in one line

The middle element becomes the root; recurse on each half.

Reach for it when: Sorted array/list to BST, unique BSTs, balance a BST.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Sorted array [-10,-3,0,5,9] to a BST. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pick the middle so both halves get the same size
2. Slice [0,4]: middle index 2 → 0 becomes the root
3. Place 0; left gets [0,1], right gets [3,4]
4. Slice [0,1]: middle index 0 → -10 becomes the left child
5. Place -10; left gets [0,-1], right gets [1,1]
6. Slice [1,1]: middle index 1 → -3 becomes the right child
7. Place -3; left gets [1,0], right gets [2,1]
8. Slice [3,4]: middle index 3 → 5 becomes the right child
9. Place 5; left gets [3,2], right gets [4,4]
10. Slice [4,4]: middle index 4 → 9 becomes the right child
11. Place 9; left gets [4,3], right gets [5,4]
12. Every slice halves, so no subtree is deeper than its sibling by more than 1
13. Each element placed once: O(n)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search Tree: BST range bounds, Inorder = sorted order, BST insert / delete / search.