[LeetCode] Problem 669 - Trim a Binary Search Tree

Posted on | In ,

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

No.1

Input: 

1
2
3
4
5
6
  1
 / \
0   2

L = 1
R = 2

Output: 

1
2
3
1
  \
   2

No.2

Input: 

1
2
3
4
5
6
7
8
9
10
  3
 / \
0   4
 \
  2
 /
1

L = 1
R = 3

Output: 

1
2
3
4
5
     3
    / 
  2   
 /
1

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode trimBST(TreeNode root, int L, int R) {
    if (root == null)
        return null;

    if (root.val > R)
        return trimBST(root.left, L, R);
    else 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;
}