💡 Problem Formulation: This article tackles the issue of pruning a binary search tree (BST) in Python to remove all nodes whose values do not fall within a specified range. Given a BST, we aim to retain only the nodes with values between low and high (inclusive), and remove any nodes outside this range. The challenge is to do so while maintaining the BST properties. We desire a resultant BST comprised only of the nodes in the specified interval.
Method 1: Recursive Trimming
This method involves writing a recursive function that traverses the BST and deletes nodes that are outside the given range. Starting at the root, the function recursively calls itself on left and right subtrees, pruning nodes as it goes, and returns a pointer to the node only if it lies within the desired range.
Here’s an example:
def trimBST(node, low, high):
if node is None:
return None
if node.val < low:
return trimBST(node.right, low, high)
if node.val > high:
return trimBST(node.left, low, high)
node.left = trimBST(node.left, low, high)
node.right = trimBST(node.right, low, high)
return node
Output:
The output will be the BST with only nodes containing values between low and high.
The code snippet defines a function trimBST which takes the root of a BST and the low and high range as arguments. It recursively traverses the tree, discarding nodes that do not fit the desired range and readjusts pointers to ensure the BST property is retained.
Method 2: Iterative Approach with Stack
This iterative method uses a stack to traverse the BST in a controlled manner. It simulates the recursive process by explicitly maintaining a stack that keeps track of nodes to visit. This allows for removal of out-of-range nodes during the traversal process.
Here’s an example:
def trimBSTIterative(root, low, high):
dummy = TreeNode(float('-inf'))
stack = [(dummy, root)]
while stack:
parent, node = stack.pop()
if node:
if node.val < low:
if parent.val < node.val:
parent.right = node.right
else:
parent.left = node.right
elif node.val > high:
if parent.val > node.val:
parent.left = node.left
else:
parent.right = node.left
else:
stack.append((node, node.right))
stack.append((node, node.left))
return dummy.right
Output:
The function returns the modified BST, having nodes only between low and high.
In this method, we declare a dummy parent node and use a stack to iterate over the tree. The key idea is to redirect parent pointers in real time when an out-of-range node is detected. This preserves the BST structure of the remaining nodes.
Method 3: Morris Traversal
Morris Traversal is a way of traversing a binary tree without using extra space for the call stack or other data structures. It modifies the tree by creating a temporary link called threaded connections and undoes these changes after the node is processed.
Here’s an example:
def trimBSTMorris(node, low, high):
# Morris Traversal-based trimming not implemented in this example
pass
Output:
Ideally, this code would output a BST with nodes in the specified range; however, an actual implementation is not provided.
While Morris Traversal is an advanced technique that reduces space complexity, it does not easily allow for deletion of nodes. As such, implementing it for this problem is more complex and is left as an exercise for readers looking for an in-depth challenge.
Method 4: Level Order Traversal and Deletion
This method employs a level order traversal (also known as breadth-first search) to access nodes in the BST. During the traversal, it checks whether each node falls within the desired range and deletes it if it does not. This method requires handling subtrees after deleting a node, which can be tricky.
Here’s an example:
def trimBSTLevelOrder(node, low, high):
# Level Order Traversal-based trimming not implemented in this example
pass
Output:
As with Morris Traversal, an actual implementation is not detailed here, but if implemented, the output would be a BST trimmed to the specified range.
Level order traversal allows for node deletion, but the real complexity lies in reconnecting the child nodes after deletion to maintain the BST properties. Due to this complexity, this method is less preferred for this task.
Bonus One-Liner Method 5: Using List Comprehension and Rebuilding the BST
Although non-conventional, this bonus method involves flattening the BST to a list using in-order traversal, filtering the list to only keep the values within the range, and then reconstructing the BST from the filtered list.
Here’s an example:
def rebuildBSTFromList(values):
# A function that would rebuild a BST from sorted list of values not implemented in this example
pass
def trimBSTOneLiner(root, low, high):
values = [node.val for node in inOrderTraversal(root) if low <= node.val <= high]
return rebuildBSTFromList(values)
Output:
The output is a new BST constructed only from nodes with values within the specified range.
Although this code snippet suggests a novel one-liner approach using a list comprehension, the real work is done by the rebuildBSTFromList function, which needs to be implemented to work correctly.
Summary/Discussion
- Method 1: Recursive Trimming. Simple and elegant. Preserves the original tree structure. Could lead to stack overflow with large trees.
- Method 2: Iterative Approach with Stack. Avoids recursion. Facilitates debugging. More complex to understand and implement than recursion.
- Method 3: Morris Traversal. Space efficient. Does not require additional memory. Difficult to implement for node deletion and not practical for this specific problem.
- Method 4: Level Order Traversal and Deletion. Works level by level. Provides a different perspective on the tree. Complicated due to the need to manage connections at every level.
- Bonus One-Liner Method 5: Using List Comprehension and Rebuilding the BST. Compact code. Hides complexity in helper function. Not efficient as it requires complete tree reconstruction.