LeetCode 669 - Trim a Binary Search Tree

https://leetcode.com/problems/trim-a-binary-search-tree/description/

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 = 2

Output: 
    1
      \
       2

Example 2:

Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

https://prismoskills.appspot.com/lessons/Binary_Trees/Remove_nodes_outside_a_given_range.jsp

TreeNode removeOutsideRange (TreeNode root, int low, int high)
{
    if (root == null)
        return;
 
    root.left  = removeOutsideRange (root.left,  low, high);
    root.right = removeOutsideRange (root.right, low, high);
 
    if (root.data < low)
        return root.right;
 
    if (root.data > high)
        return root.left;
 
    return root;
}

https://leetcode.com/problems/trim-a-binary-search-tree/solution/

• Time Complexity: $O(N)$, where $N$ is the total number of nodes in the given tree. We visit each node at most once.
• Space Complexity: $O(N)$. Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.

  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;

  }

public TreeNode trimBST(TreeNode root, int L, int R) {

if (root == null) {

return null;

}

TreeNode newRoot = null;

if (root.val >= L && root.val <= R) { // not root.val <= L && root.val >= R

newRoot = root;

}

TreeNode left = null;

if (root.val >= L) {

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

}

TreeNode right = null;

if (root.val <= R) {

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

}

if (newRoot != null) {

newRoot.left = left;

newRoot.right = right;

} else {

if (left != null) {

newRoot = left;

// right would be null

// BUG newRoot.right = right;

} else {

// left would be null

newRoot = right;

}

}

return newRoot;

}

https://leetcode.com/problems/trim-a-binary-search-tree/discuss/107026/Java-solution-iteration-version
one for finding a new root. Second for removing the invalid nodes from left subtree of new root. The last one for removing the invalids nodes from right subtree of new root

    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return root;
        }
        //Find a valid root which is used to return.
        while (root.val < L || root.val > R) {
            if (root.val < L) {
                root = root.right;
            }
            if (root.val > R) {
                root = root.left;
            }
        }
        TreeNode dummy = root;
        // Remove the invalid nodes from left subtree.
        while (dummy != null) {
            while (dummy.left != null && dummy.left.val < L) {
                dummy.left = dummy.left.right; 
                // If the left child is smaller than L, then we just keep the right subtree of it. 
            }
            dummy = dummy.left;
        }
        dummy = root;
        // Remove the invalid nodes from right subtree
        while (dummy != null) {
            while (dummy.right != null && dummy.right.val > R) {
                dummy.right = dummy.right.left;
                // If the right child is biggrt than R, then we just keep the left subtree of it. 
            }
            dummy = dummy.right;
        }
        return root;
    }