Sponsored
Sponsored
We can utilize the properties of a BST to perform a recursive traversal. The strategy here involves:
low, we need to trim the left subtree and consider the right subtree.high, we trim the right subtree and consider the left subtree.low, high], we recursively trim both subtrees.Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
9 if not root:
10 return None
11 if root.val < low:
12 return self.trimBST(root.right, low, high)
13 if root.val > high:
14 return self.trimBST(root.left, low, high)
15 root.left = self.trimBST(root.left, low, high)
16 root.right = self.trimBST(root.right, low, high)
17 return rootPython implementations directly return the recursive results based on the current node's value compared to the bounds.
This iterative approach uses a stack to traverse the tree. The main idea is to mimic the recursive depth-first search using an explicit stack.
Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.
1import java.util.Stack;
This Java example shows an iterative approach using a stack to maintain the modified tree's structure while keeping nodes within bounds. Each node is processed, ensuring valid nodes are stacked for later traversal.