DSA problem
Balance a Binary Search Tree
Given the root of a Binary Search Tree (BST), return a balanced binary search tree with the same node values. A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than one. If there is more than one valid answer, you may return any of them.
A natural but wrong instinct is to try local rotations until the tree looks balanced. Self-balancing schemes like AVL or Red-Black trees do exactly that, but they are complex to implement and not necessary here. The problem grants us complete freedom to rebuild the tree from scratch, so we should take advantage of that.
The simplest correct strategy has two phases. Phase 1: perform an inorder traversal of the input BST, collecting node values into an array. Because the input is a valid BST, this array is sorted in ascending order — no extra sort needed. Phase 2: recursively build a balanced BST from this sorted array by always choosing the middle element as the subtree root. Pick the middle index, make it the root, build the left subtree from values before it, and the right subtree from values after it.
Choosing the middle as the root guarantees a height-balanced result: each side of the split has at most one more element than the other, so the recursion depth differs by at most one between siblings. Both phases are O(n) time, and the total space is O(n) for the auxiliary array and the recursion stack — both unavoidable since the problem requires producing n new nodes.
Examples
root = [1,null,2,null,3,null,4,null,null][2,1,3,null,null,null,4]root = [2,1,3][2,1,3]root = [10,5,15,3,8,null,20][8,5,15,3,null,10,20]Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= Node.val <= 10^5
- The input is guaranteed to be a valid BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.