# Trim a Binary Search Tree

• thank you~ nice job~

• Exactly what I did. So proud of myself :)

• Heroes see same things haha!

• Should we consider the "boundary" cases? like
root.left == L or
root.right == R

we could terminate the loop early if we check the boundary cases.

For example,

```         3
/          \
0           100
\           /
2         99
/         /
1        98
/
...
```

// Correct me if I am wrong....
Thanks.

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {

if (root==null){
return null;
}
if ((root.val>=L && root.val<=R)) {
root.left= trimBST(root.left, L, R);
root.right=trimBST(root.right,  L,  R);
}
else if(root.val<L){
root = trimBST(root.right,L,R);
}else if (root.val>R){
root=trimBST(root.left,L,R);
}
return root;
}
}``````

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution
{
public TreeNode trimBST(TreeNode root, int L, int R)
{
// if root is null its obvious that we need to return null
if (root == null)
{
return null;
}

// if root value itself is equal to lowest value range, then complete left side of tree can be discarded.
if (root.val == L)
{
root.left = null;
root.right = trimBST(root.right, L, R);
return root;
}

// if root value itself is equal to highest value range, then complete left side of tree can be discarded.
if (root.val == R)
{
root.right = null;
root.left = trimBST(root.left, L, R);
return root;
}

// if lowest and highest value both are greater than root then we know value we need remains at the right side of the tree. So trim right side.
if (root.val < L && root.val < R)
{
return trimBST(root.right, L, R);
}

// if lowest and highest value both are less than root then we know value we need remains at the left side of the tree. So trim left side.
if (root.val > L && root.val > R)
{
return trimBST(root.left, L, R);
}

// if all these conditions fail then we are sure that it is between left and right side of tree. So trim both

root.right = trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);

return root;

}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.