# 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.

Input:
5
/ \
3 6

L = 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 vice-versa. If both conditions fail, then we have to trim both sides of the tree.

### 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).
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]