## 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 vice-versa. 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).