Given the root of a binary search tree, return a balanced binary search tree with the same values, where the depths of every node's two subtrees differ by at most one. Any valid answer is accepted.
Before you code
The input may be a chain. Which traversal produces the keys in sorted order, and what do you do with sorted keys?
Hints
- Collect the values with an in-order traversal, iteratively if the tree may be deep. They come out sorted.
- Rebuild with the middle value as the root, recursively, in O(n).
- Compare with inserting the values one by one into an AVL tree, with rotations: O(n log n), but it keeps working as new keys arrive.
Production & complexity notes
When solving Balance a binary search tree on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in AVL rotations to reinforce the underlying pattern.
What it practices
The balance invariant, and the two ways of restoring it, from AVL rotations.