Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one 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 1:
Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.
Example 2:
Input: root = [2,1,3] Output: [2,1,3]
Constraints:
[1, 104].1 <= Node.val <= 105Problem Overview: You receive the root of a binary search tree that may be heavily skewed. The task is to return a height-balanced BST containing the same node values. A balanced tree keeps the height difference between left and right subtrees small, ensuring operations like search and insertion remain efficient.
Approach 1: In-order Traversal and Rebuilding (O(n) time, O(n) space)
A binary search tree has one critical property: an in-order traversal visits nodes in sorted order. Traverse the tree using DFS and store all node values in an array. Once you have the sorted list, build a new balanced BST by repeatedly selecting the middle element as the root. Recursively construct the left subtree from the left half and the right subtree from the right half. This guarantees minimal height because each level splits the data roughly in half. Time complexity is O(n) since every node is visited once and reconstructed once. Space complexity is O(n) for the array plus recursion stack.
This approach is widely used because it is simple and reliable. It converts the structural problem of balancing a tree into a sorted-array construction problem. The traversal step relies on Depth-First Search, while the reconstruction mirrors classic balanced BST creation techniques from a sorted list.
Approach 2: Divide-And-Conquer Direct Construction (O(n) time, O(n) space)
The second approach still relies on the sorted nature of BST traversal but emphasizes the Divide and Conquer pattern more explicitly. First perform an in-order traversal to collect nodes. Instead of only storing values, you can reuse the node objects themselves. Recursively choose the middle node as the root, attach the left half as the left subtree and the right half as the right subtree. Each recursive step splits the array into two halves, ensuring the resulting tree remains balanced.
This technique ensures each node participates in exactly one recursive construction step. Time complexity remains O(n). Space complexity is O(n) due to storing the traversal and recursion depth. Because the algorithm repeatedly divides the sorted sequence, it naturally produces a balanced structure.
Both approaches rely on the core property of a Binary Search Tree: sorted order from in-order traversal. Once the values are sorted, building a balanced BST becomes a deterministic recursive process.
Recommended for interviews: The in-order traversal plus rebuild approach is the expected solution. It demonstrates understanding of BST properties and balanced tree construction while keeping the implementation clean. Interviewers often accept both variants, but showing the sorted-array reconstruction pattern clearly signals strong grasp of tree traversal and divide-and-conquer thinking.
This approach involves performing an in-order traversal of the binary search tree to collect its node values in sorted order. Since the values are sorted, we can then use the sorted list to construct a balanced binary search tree. The central idea is that the middle element of the sorted list becomes the root of the tree, and recursively the middle element of each sublist becomes the root of the subtrees, thereby ensuring balanced condition.
The code first defines a TreeNode structure to represent each node of the binary search tree. The inorder function performs the in-order traversal, collecting values into an array. Then, the buildTree function constructs a balanced tree from this array. The balanceBST function orchestrates the process by first collecting nodes and then building and returning the balanced tree.
Time Complexity: O(n), where n is the number of nodes in the BST, for the in-order traversal and subsequent tree construction.
Space Complexity: O(n), for storing the node values in an array.
This alternative approach aims to build a balanced BST directly from the given BST by using a divide-and-conquer strategy. The process involves using in-order traversal to fetch node values, converting it to a sorted array, and recursively constructing the entire balanced tree directly. While the initial step is similar, this approach focuses on minimizing operations by targeting balanced construction upfront.
The C solution capitalizes on a similar foundational logic by conducting an in-order traversal to offer node values in sorted form. With arrays handling value storage, the createBalancedTree function exploits mid-index calculations to orchestrate BST construction in a balance-focused manner.
Time Complexity: O(n), anchored in initial traversal and full reconstruction.
Space Complexity: O(n), stemming from node value arrays.
| Approach | Complexity |
|---|---|
| In-order Traversal and Rebuilding | Time Complexity: O(n), where n is the number of nodes in the BST, for the in-order traversal and subsequent tree construction. |
| Divide-And-Conquer Direct Construction | Time Complexity: O(n), anchored in initial traversal and full reconstruction. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-order Traversal and Rebuilding | O(n) | O(n) | Most common approach. Easy to implement and guarantees a balanced BST using a sorted array. |
| Divide-and-Conquer Direct Construction | O(n) | O(n) | Preferred when emphasizing divide-and-conquer recursion or reusing node objects instead of values. |
Balance a Binary Search Tree | Leetcode #1382 • Techdose • 19,573 views views
Watch 9 more video solutions →Practice Balance a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode