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 <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 306,385 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