Given the root of a binary search tree, return a balanced binary search tree that contains the same node values. If there is more than one valid answer, return any of them.
A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
Example:
Input: root = [1, null, 2, null, 3, null, 4, null, null]
Output: [2, 1, 3, null, null, null, 4]
(Other balanced shapes with the same values are also acceptable.)
Do an in-order traversal to collect nodes in sorted order, then build a balanced BST from the sorted list using the standard sorted-array → BST recursion (pick mid as root). Time O(n), extra space O(n).
The VOprep team has long accompanied candidates through various major company OAs and VOs, including OpenAI, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
