The problem
Given a possibly unbalanced BST, return a height-balanced BST containing the same values.
Stuck? Reveal hints one at a time
How to approach it
- 1Inorder-traverse the tree, collecting values into a sorted array.
- 2Rebuild with the midpoint-recursion trick: middle element becomes root, halves become subtrees.
- 3Return the new root.
Key insight
Flatten-then-rebuild sidesteps rotation bookkeeping entirely — a global O(n) rebalance versus AVL’s incremental local fixes.
The solution
Watch out for
- This is the offline answer; ongoing inserts need a genuinely self-balancing tree (AVL/red-black).
- A degenerate input chain can be n deep — iterative inorder avoids recursion overflow.