LeetCode-1382: Balancing a Binary Search Tree - A Comprehensive Guide
The Challenge: Imagine you have a Binary Search Tree (BST) that's been haphazardly built. It's quite possible it's become lopsided and inefficient. Your task is to take this messy tree and transform it into a balanced one, maintaining the original order of the nodes.
Rephrased: Given a Binary Search Tree, we need to restructure it into a perfectly balanced BST while preserving the original order of its elements. This means every node in the resulting tree should be as close as possible to having an equal number of nodes in its left and right subtrees.
Scenario and Code:
Let's consider the following example:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)
root.right.right.right.right = TreeNode(5)
This tree is highly unbalanced, with all the nodes on the right side. Our objective is to balance this tree, effectively creating a more efficient search structure.
def balanceBST(root):
# ... (code to implement the solution goes here)
Solution and Analysis:
The key to balancing a BST is to convert the original tree into a sorted list and then reconstruct a balanced tree from this list. Here's a breakdown of the solution:
- Convert to Sorted List: We perform an inorder traversal of the original tree, storing the node values in a sorted list.
- Construct Balanced Tree: We then use a recursive function to construct a balanced tree from the sorted list. This function works as follows:
- Base Case: If the list is empty, return
None. - Recursive Step: Find the middle element of the list, create a new node with that value, and recursively construct the left subtree from the elements before the middle and the right subtree from the elements after the middle.
- Base Case: If the list is empty, return
Code Implementation:
def balanceBST(root):
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
def constructBST(nums, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(nums[mid])
node.left = constructBST(nums, start, mid - 1)
node.right = constructBST(nums, mid + 1, end)
return node
nums = inorder(root)
return constructBST(nums, 0, len(nums) - 1)
Further Insights:
- Time Complexity: The inorder traversal takes O(N) time, and the construction of the balanced tree also takes O(N) time, resulting in an overall time complexity of O(N).
- Space Complexity: The space complexity is dominated by the sorted list, which requires O(N) space.
- Applications: Balancing BSTs is crucial in various applications like databases, search engines, and file systems, where efficient search and retrieval are essential.
In Conclusion: Balancing a BST is a common problem in computer science, and this approach provides a clear and efficient solution. By converting the tree to a sorted list and then reconstructing a balanced tree, we can ensure optimal performance for searching and retrieval operations.
Resources:
