Problem

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 1:

Input:     1   / \  0   2  L = 1  R = 2Output:     1      \       2

Example 2:

Input:     3   / \  0   4   \    2   /  1  L = 1  R = 3Output:       3     /    2     / 1

Solution

Recursive

class Solution {    public TreeNode trimBST(TreeNode root, int L, int R) {        if (root == null || L > R) return null;        if (root.val > R) return trimBST(root.left, L, R);        if (root.val < L) return trimBST(root.right, L, R);        if (root.val >= L && root.val <= R) {            root.left = trimBST(root.left, L, R);            root.right = trimBST(root.right, L, R);        }        return root;    }}

Iterative

class Solution {    public TreeNode trimBST(TreeNode root, int L, int R) {        if (root == null) return null;        while (root.val < L || root.val > R) {            if (root.val < L) {                root = root.right;            }            if (root.val > R) {                root = root.left;            }        }        TreeNode dummy = root;        while (dummy != null) {            while (dummy.left != null && dummy.left.val < L) {                dummy.left = dummy.left.right;            }            dummy = dummy.left;        }                dummy = root;        while (dummy != null) {            while (dummy.right != null && dummy.right.val > R) {                dummy.right = dummy.right.left;            }            dummy = dummy.right;        }                return root;    }}