Java

/**

 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

 */
public class Trim_a_Binary_Search_Tree {

    /*

         Input:
           1
          / \
         0   2

         L = 0
         R = 0

        Output:
         0
     */


    /**
     * 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) {

            // basic rule: if root is deleted, the move right to be new root

            if (root == null) {
                return null;
            }

            if (root.val < L) {
                // then all its left children are less than L, only return right child
                root = trimBST(root.right, L, R);
            }

            else if (root.val > R) {
                // then all its right children bigger than R, and disgarded
                root = trimBST(root.left, L, R);
            }

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

            return root;
        }
    }
}

// OJ: https://leetcode.com/problems/trim-a-binary-search-tree/
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;
        if (root->val < L) return trimBST(root->right, L, R);
        if (root->val > R) return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        if not root:
            return None
        if L > root.val:
            return self.trimBST(root.right, L, R)
        elif R < root.val:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

Java

/**
 * 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) {
        while (root != null && root.val < L)
            root = root.right;
        if (root == null)
            return null;
        TreeNode parentLeft = root, childLeft = root.left;
        while (childLeft != null) {
            if (childLeft.val < L) {
                parentLeft.left = childLeft.right;
                childLeft = childLeft.right;
            } else {
                parentLeft = childLeft;
                childLeft = childLeft.left;
            }
        }
        while (root != null && root.val > R)
            root = root.left;
        if (root == null)
            return null;
        TreeNode parentRight = root, childRight = root.right;
        while (childRight != null) {
            if (childRight.val > R) {
                parentRight.right = childRight.left;
                childRight = childRight.left;
            } else {
                parentRight = childRight;
                childRight = childRight.right;
            }
        }
        return root;
    }
}

// OJ: https://leetcode.com/problems/trim-a-binary-search-tree/
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;
        if (root->val < L) return trimBST(root->right, L, R);
        if (root->val > R) return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        if not root:
            return None
        if L > root.val:
            return self.trimBST(root.right, L, R)
        elif R < root.val:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

669 - Trim a Binary Search Tree

All Problems

All Solutions