Balance a Binary Search Tree
Medium · Binary Search Trees · about 20 minutes
Asked at Google, Amazon, Microsoft, Meta.
Rebuild a binary search tree so it holds the same values but every node's two subtrees differ in height by at most one. Return the new root.