Balance a Binary Search Tree: Inorder + Rebuild

You are given the root of a binary search tree. Return a balanced binary search tree with the same node values. A balanced BST is one where the depth of the two subtrees of every node never differs by more than 1. If there is more than one answer, return any of them.

This is LeetCode 1382: Balance a Binary Search Tree, and it combines two classic tree techniques into one clean solution. If you have seen "Convert Sorted Array to BST" before, you already know half the answer.

Why this problem matters

Unbalanced BSTs come up constantly in practice. If you insert sorted data into a naive BST, you get a linked list with O(n) lookups instead of O(log n). Real-world databases use self-balancing trees (AVL, red-black) to prevent this. This problem asks you to do it manually: take a skewed tree and rebuild it into a balanced one.

The technique also shows up in interview variations. You might be asked to "rebalance a BST after deletions" or "optimize a BST that has degraded." The approach is always the same: flatten it, then rebuild it.

The key insight

An inorder traversal of any BST produces a sorted array. Once you have the sorted array, building a balanced BST from it is a solved problem: pick the middle element as the root, recurse on the left half for the left subtree, and recurse on the right half for the right subtree.

So the algorithm is two steps:

1. Inorder traversal to extract the sorted values.
2. Divide and conquer to build the balanced tree from those sorted values.

That is the entire solution. No rotations, no AVL balancing factors, no red-black recoloring. Just flatten and rebuild.

The solution

def balanceBST(root):
    nodes = []

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        nodes.append(node)
        inorder(node.right)

    def build(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = nodes[mid]
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node

    inorder(root)
    return build(0, len(nodes) - 1)

The inorder function walks the tree left-root-right and appends every node to a list. Because it is a BST, the list ends up sorted. The build function takes a range [lo, hi] and picks the middle index as the root. It then recursively builds the left subtree from elements before the middle and the right subtree from elements after the middle. This guarantees the resulting tree is height-balanced.

Notice that we reuse the existing tree nodes instead of creating new ones. We just reassign their left and right pointers. This keeps the solution clean and avoids unnecessary memory allocation.

Visual walkthrough

Here is the full trace for the tree 1 -> 2 -> 3 -> 4 (right-skewed):

• Inorder traversal visits nodes in order: 1, 2, 3, 4. The sorted array is [1, 2, 3, 4].
• build(0, 3): mid = 1, root = node 2. Left: build(0, 0). Right: build(2, 3).
• build(0, 0): mid = 0, root = node 1. No children. Returns leaf node 1.
• build(2, 3): mid = 2, root = node 3. Left: build(2, 1) returns None. Right: build(3, 3).
• build(3, 3): mid = 3, root = node 4. No children. Returns leaf node 4.

The final tree has 2 at the root, 1 as its left child, 3 as its right child, and 4 as the right child of 3. Every subtree is balanced.

Complexity analysis

Time is O(n). The inorder traversal visits every node once, which is O(n). The build phase also visits every node once to place it in the balanced tree. Total: O(n) + O(n) = O(n).

Space is O(n). The nodes list stores all n nodes. The recursion stack for both the inorder traversal and the build phase goes up to O(log n) in depth for a balanced tree, but the list itself dominates at O(n). If the input tree is completely skewed, the inorder recursion stack is also O(n), but the list already accounts for that.

The building blocks

1. Inorder traversal to flatten a BST

def inorder(node):
    if not node:
        return
    inorder(node.left)
    nodes.append(node)
    inorder(node.right)

Inorder traversal of a BST always produces values in sorted order. This is because BST property guarantees left values are smaller and right values are larger. Walking left-root-right visits everything in ascending order. You will see this pattern in problems like Validate BST, Kth Smallest Element in a BST, and BST Iterator.

2. Build a balanced BST from a sorted sequence

def build(lo, hi):
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = nodes[mid]
    node.left = build(lo, mid - 1)
    node.right = build(mid + 1, hi)
    return node

Picking the middle element as the root and recursing on both halves is the same divide-and-conquer technique used in Convert Sorted Array to BST (LeetCode 108). It guarantees balance because each half differs in size by at most one element. This pattern also appears when constructing segment trees and balanced partitions.

Edge cases

• Single node: the tree is already balanced. Inorder produces [root], and build returns it as a leaf.
• Already balanced: the algorithm still works. It flattens and rebuilds, producing a valid balanced tree (possibly with a different structure than the input).
• Left-skewed tree: same approach. Inorder still produces sorted order regardless of the shape.
• Two nodes: [a, b] with mid = 1 produces root = b with left child a, or mid = 0 produces root = a with right child b. Both are valid balanced BSTs.
• All nodes have the same value: the BST property allows duplicates in some definitions. The algorithm still works because inorder traversal preserves order.

From understanding to recall

You just saw how two classic techniques, inorder traversal and sorted-array-to-BST, combine to solve a problem that sounds intimidating at first. The idea is clean: flatten the tree into sorted order, then rebuild it balanced. No rotations needed.

But knowing the idea and being able to code it under pressure are different things. Will you remember to use index-based recursion with lo and hi instead of slicing? Will you remember to reuse the existing nodes instead of creating new ones? These details matter in an interview.

Spaced repetition helps you lock in the full solution. You practice writing it from scratch at increasing intervals, until the inorder-then-rebuild pattern becomes automatic. After a few reps, you will not just remember the approach, you will be able to adapt it to variations like "balance a BST after a series of insertions" without hesitation.

Related posts

• Validate Binary Search Tree - Tests whether a tree satisfies the BST property, the same property this problem preserves during rebalancing
• Convert Sorted Array to Binary Search Tree - The second half of this problem's solution, building a balanced BST from sorted data
• Invert Binary Tree - Another tree transformation problem that modifies pointers in place

CodeBricks helps you build lasting fluency with patterns like inorder-then-rebuild through spaced repetition. Instead of solving a problem once and forgetting the details, you practice at the right intervals until the pattern sticks.