Balance a BST

Balance a Binary Search Tree takes a valid but lopsided BST and rebuilds it so its height is as small as possible. It is a clean two-phase problem that rewards knowing one fact cold: an in-order walk of a BST yields its values in sorted order.

The slow way first

You could try rotating nodes in place (the AVL/red-black approach), but that is fiddly and easy to get wrong under interview pressure. A naive alternative — repeatedly insert values into a fresh tree — can itself produce another skewed tree if you insert in sorted order, so it solves nothing.

The question to ask: what is the cheapest way to get a perfectly balanced shape? If we had the values in a sorted array, the answer is mechanical — and a BST already hands us sorted values for free.

The idea: flatten, then rebuild from the middle

Two phases. Phase 1: do an in-order traversal to flatten the tree into a sorted array. Phase 2: build a new BST from that array by always taking the middle element as the subtree root, then recursing on the left half and the right half. Choosing the middle guarantees each side gets (almost) the same number of values, which is exactly what balance means.

The key insight: the middle of a sorted range is the only choice that keeps the two sides equal in size, so the recursion produces a height-balanced tree automatically.

Walk through it

Step through the animation. First the in-order traversal reveals the values 1..7 into a sorted row. Then the mid pointer scans that row: index 3 (value 4) becomes the root, the middle of the left half (2) and right half (6) become its children, and the single leftover elements become the leaves. The skewed chain of height 7 collapses into a balanced tree of height 3.

Pseudocode

arr = []
inorder(root):                 # left, node, right -> sorted values
    if node is None: return
    inorder(node.left)
    arr.append(node.val)
    inorder(node.right)
 
build(lo, hi):                 # build a balanced BST from arr[lo..hi]
    if lo > hi: return None
    mid = (lo + hi) // 2
    node = new TreeNode(arr[mid])
    node.left  = build(lo, mid - 1)
    node.right = build(mid + 1, hi)
    return node
 
return build(0, len(arr) - 1)

The Python solution

def balance_bst(root):
    arr = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)
    def build(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(arr[mid])
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(arr) - 1)

• arr collects the values; the nested inorder appends them left → node → right, so they land sorted.
• inorder(root) runs phase 1 and fills arr.
• build(lo, hi) rebuilds a balanced BST from the slice arr[lo..hi].
• if lo > hi is the base case — an empty range returns None (a missing child).
• mid = (lo + hi) // 2 picks the middle so both sides get equal counts; arr[mid] becomes this subtree root.
• The two recursive build calls attach the balanced left and right subtrees, then we return node.

Complexity

We use O(n) extra space for the array plus O(log n) recursion stack for the balanced build (or O(n) on the skewed input traversal). Both phases are linear, so the whole rebuild is O(n).

When this pattern shows up

Practice