Balance a Binary Search Tree
Understanding the Problem
A binary search tree orders its values by structure, but the structure itself can be arbitrarily lopsided. In the worst case every node has only a right child and the tree is a chain, so search, insert, and delete all degrade from O(log n) to O(n). The task is to rebuild the tree with the same values so that no node's left and right subtrees differ in height by more than 1.
No values change; only the links between nodes do. The BST property is what makes the rebuild manageable: an inorder traversal visits the values in sorted order, and a sorted sequence converts to a balanced BST by repeatedly choosing the middle element as the root and recursing on the two halves.
Key Constraints:
1 <= number of nodes <= 10^4→ O(n) and O(n log n) solutions both run well within limits.1 <= Node.val <= 10^5→ Values fit in a 32-bit integer, so there are no overflow concerns in any approach.
Approach 1: Collect Values + Sort + Rebuild
Intuition
Ignore the BST property and treat the input as an arbitrary binary tree: collect every value with any traversal, sort the list, and build a balanced BST from the sorted result with divide and conquer.
Building from a sorted array produces a balanced tree because the middle element becomes the root, splitting the remaining values into two halves whose sizes differ by at most one. Each half is built the same way and becomes one subtree. Two subtrees whose sizes differ by at most one also differ in height by at most one, and the same argument applies at every node further down. The BST ordering holds as well: everything left of the middle is smaller than the root, everything right of it is larger.
Algorithm
- Traverse the entire tree (any order works: preorder, inorder, level order) and collect all node values into a list.
- Sort the list in ascending order.
- Build a balanced BST from the sorted list using divide and conquer:
- Base case: if the range is empty, return null.
- Pick the middle element as the root.
- Recursively build the left subtree from the left half.
- Recursively build the right subtree from the right half.
- Return the root of the new tree.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). Traversing the tree takes O(n). Sorting the collected values takes O(n log n). Building the balanced BST takes O(n). The sorting step dominates.
- Space Complexity: O(n). The list stores all n values. The collection recursion adds O(h), where h is the height of the input tree (O(n) worst case for a skewed tree), and the build recursion adds O(log n). The list dominates.
The sort is the bottleneck, and for a BST it is unnecessary: an inorder traversal visits the values in ascending order on its own.
Approach 2: Inorder Traversal + Divide and Conquer
Intuition
An inorder traversal of a BST (left subtree, then root, then right subtree) visits values in ascending order: every value in a node's left subtree is smaller than the node, every value in its right subtree is larger, and the same holds recursively below. Collecting values during an inorder traversal therefore yields a sorted list directly, and the O(n log n) sort from Approach 1 disappears.
The rebuild step is identical to Approach 1: the middle element becomes the root, the left half becomes the left subtree, and the right half becomes the right subtree.
Algorithm
- Perform an inorder traversal of the BST to collect all node values into a sorted list.
- Build a balanced BST from the sorted list using divide and conquer:
- Base case: if
left > right, return null. - Compute
mid = left + (right - left) / 2. - Create a new node with
values[mid]. - Recursively build the left subtree from
values[left..mid-1]. - Recursively build the right subtree from
values[mid+1..right]. - Return the root of the new tree.
Visualization and Code
Loading animation...
- Time Complexity: O(n). The inorder traversal visits each node exactly once, taking O(n). The rebuild step also processes each value exactly once, taking O(n). Total: O(n).
- Space Complexity: O(n). The list stores all n values. The inorder recursion adds O(h), where h is the height of the input tree (O(n) worst case for a skewed tree), and the build recursion adds O(log n). The list dominates.
The running time is now optimal, but the values list still costs O(n) extra memory, and it exists only to feed the builder one sorted value at a time. The next approach produces those values on demand instead of storing them.
Approach 3: Build from an Inorder Iterator
Intuition
The sorted list in Approach 2 serves a single purpose: handing the builder the next value in ascending order each time it creates a node. A stack-based inorder iterator over the original tree serves the same requests without materializing the list.
The iterator is the standard one for iterative inorder traversal. Push the root and all of its left descendants onto a stack; the top of the stack is then the smallest unvisited node. After popping a node, push the leftmost path of its right subtree, and the new top is the next value in order. Each node is pushed and popped exactly once over the whole run.
The builder changes from indexing into an array to consuming a stream. build(size) constructs a balanced subtree of exactly size nodes: it builds a left subtree of size / 2 nodes, pops one node from the iterator to act as the root, then builds a right subtree from the remaining size - size / 2 - 1 nodes. The recursion fills positions in left-root-right order, which is the inorder sequence of the tree being built. The iterator supplies values in ascending order, so the k-th smallest value lands in the k-th inorder position of a balanced shape, and the result is a valid balanced BST. A counting pass runs first so that build(n) knows how many values it owns.
When size is even, this builder roots the subtree at the value after the first size / 2, so its output can differ from Approach 2's tree. The problem accepts any balanced arrangement.
Algorithm
- Count the nodes in the tree; call the total
n. - Push the root and every node on its leftmost path onto the iterator stack.
- Call
build(n), wherebuild(size)works as follows: - If
sizeis 0, return null. - Build the left subtree with
build(size / 2). - Pop a node from the stack, create a new node with its value, and push the leftmost path of the popped node's right child onto the stack.
- Build the right subtree with
build(size - size / 2 - 1). - Attach both subtrees and return the new node.
- The tree returned by
build(n)is the answer.
Visualization and Code
Loading animation...
- Time Complexity: O(n). The counting pass visits each node once. During the build, every original node is pushed and popped exactly once, and every new node is created once.
- Space Complexity: O(h + log n) auxiliary, where h is the height of the input tree. The counting recursion and the iterator stack each hold at most one root-to-leaf path of the original tree (O(n) worst case for a skewed tree), and the build recursion is O(log n) because the tree it builds is balanced. The new tree itself is the required output, not auxiliary space.
Auxiliary space now depends on the input tree's height rather than always being O(n), but a degenerate input still costs O(n). The Day-Stout-Warren algorithm removes the dependence entirely by rebalancing the existing nodes in place.
Approach 4: DSW Algorithm (In-Place)
Intuition
The Day-Stout-Warren (DSW) algorithm balances the tree in place: no array, no recursion, O(1) extra space. It is also the only approach here that relinks the existing nodes instead of allocating new ones. It runs in two phases built entirely from rotations.
Phase 1 - Tree to vine: Convert the tree into a vine, a chain in which every node has only a right child and the values appear in sorted order. Walk down the right spine; whenever the current node has a left child, apply a right rotation, which lifts the left child into the current node's position and pushes the current node down to its right. A rotation rearranges a constant number of pointers and preserves the BST ordering, so once no left children remain, the chain is sorted.
Phase 2 - Vine to balanced tree: Fold the vine into a balanced tree with passes of left rotations. A pass of k rotations walks the spine lifting every other node and tucking the node above it underneath as a left child, so each pass roughly halves the spine and finishes one level of the tree. The first pass needs special sizing: unless n has the form 2^k - 1 (a perfect tree size), the leftover nodes must become the bottom, partially filled level of leaves, so the first pass performs exactly that many rotations before the halving passes start.
Algorithm
- Create a dummy node whose right child is the actual root, so rotations at the root need no special case.
- Phase 1 (Tree to Vine): Walk the right spine starting from the dummy. If the current node has a left child, right-rotate to lift that child. Otherwise count the node and advance. The result is a sorted right-only chain of n nodes.
- Phase 2 (Vine to Balanced Tree):
- Compute
m, the size of the largest perfect binary tree with at most n nodes: the largest value of the form 2^k - 1 that is at most n. - Perform
e = n - mleft rotations along the vine starting from the dummy. The e demoted nodes become the bottom level of the final tree. - Set
remaining = m. Whileremaining > 1, halve it (integer division) and perform that many left rotations starting from the dummy. - Return the dummy's right child.
In Phase 1, each right rotation lifts a left child onto the right spine while the demoted node stays on the spine below it. The spine gains one node per rotation and never loses one, so Phase 1 performs at most n - 1 rotations before every node sits on the spine. Rotations preserve BST ordering, so the finished vine is sorted.
The Phase 2 pass sizes come from the target shape. A perfect tree of m = 2^k - 1 nodes falls out of the halving passes alone: each pass lifts alternate spine nodes, halving the spine and completing one level, and after k passes the spine is a single node, the root. When n is not a perfect size, the e = n - m leftover nodes must form the partial bottom level. The first pass of e rotations demotes exactly e nodes into left-child positions, where they remain as the deepest leaves, and leaves a spine of m nodes for the halving passes. The choice of m guarantees e <= m (since n <= 2m), so the vine is always long enough for that first pass.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Phase 1 performs at most n - 1 rotations, since each rotation adds one node to the right spine and the spine holds at most n nodes. Phase 2 performs fewer than n rotations across all passes (e in the first pass, then m/2 + m/4 + ... + 1). Each rotation updates a constant number of pointers.
- Space Complexity: O(1). A constant number of pointer variables, no recursion, no arrays. The algorithm relinks the existing nodes in place.
DSW is a one-time global rebalance for a tree that has already degraded. Systems that must keep a tree balanced under continuous inserts and deletes use self-balancing structures such as AVL or red-black trees instead, paying O(log n) rotation work on every update so a full O(n) rebuild is never needed.