Sponsored
Sponsored
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.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def inorder(self, root, nodes):
9 if root:
10 self.inorder(root.left, nodes)
11 nodes.append(root.val)
12 self.inorder(root.right, nodes)
13
14 def buildTree(self, nodes, start, end):
15 if start > end:
16 return None
17 mid = (start + end) // 2
18 node = TreeNode(nodes[mid])
19 node.left = self.buildTree(nodes, start, mid - 1)
20 node.right = self.buildTree(nodes, mid + 1, end)
21 return node
22
23 def balanceBST(self, root):
24 nodes = []
25 self.inorder(root, nodes)
26 return self.buildTree(nodes, 0, len(nodes) - 1)The Python solution is structured similarly, with an inorder method to gather node values, and a buildTree method to recursively construct the balanced BST from the sorted values.
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.
Time Complexity: O(n), anchored in initial traversal and full reconstruction.
Space Complexity: O(n), stemming from node value arrays.
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.