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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode TrimBST(TreeNode root, int low, int high) {
10 if (root == null) return null;
11 if (root.val < low) return TrimBST(root.right, low, high);
12 if (root.val > high) return TrimBST(root.left, low, high);
13 root.left = TrimBST(root.left, low, high);
14 root.right = TrimBST(root.right, low, high);
15 return root;
16 }
17}The C# solution uses similar recursion logic to adjust and trim the BST based on the node values compared to the given 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.
1class TreeNode:
2
The Python solution employs a stack for an iterative node traversal. Adjustments are made according to the node values relative to low and high. Nodes are appended to a stack for traversal if they are valid.