Trim A Binary Search Tree

Trim a Binary Search Tree

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:

Input:
5
/ \
3 6

L = 5 R = 7

Output:
5
\
6

Solution:

We traverse through the whole tree while checking if the current node value < R or value > L. If first condition is not true then we conclude that the trim must occur to hte left of the node and vice-versa. If both conditions fail, then we have to trim both sides of the tree.

Implementation:

Java:

class Solution1 {
    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;
    }
}

Complexity Analysis:

• Time Complexity: O(N), where NN is the total number of nodes in the given tree.
• Space Complexity: O(N).