Trim a Binary Search Tree
Given a binary search tree and the lowest and highest boundaries as L
and R
, trim the tree so that all its elements lies in [L, R]
(R >= L)
. You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example:
Input:
5
/ \
3 6L = 5 R = 7
Output:
5
\
6
Solution:
We traverse through the whole tree while checking if the current node value < R or value > L. If first condition is not true then we conclude that the trim must occur to hte left of the node and viceversa. If both conditions fail, then we have to trim both sides of the tree.
Implementation:
Java:
class Solution1 {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return root;
}
if (root.val > R) {
return trimBST(root.left, L, R);
}
if (root.val < L) {
return trimBST(root.right, L, R);
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
Complexity Analysis:

Time Complexity: O(N), where NN is the total number of nodes in the given tree.

Space Complexity: O(N).