algoadvance

Leetcode 669. Trim a Binary Search Tree

Problem Statement

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lie in [low, high]. Trimming the tree should not change the relative structure of the remaining nodes. It should be a new tree that satisfies the given bounds.

Clarifying Questions

1. Can the values of the nodes and the boundaries be negative?
   • Yes, both node values and boundaries can be negative.
2. What should we return if no node falls within the bounds?
   • Return null if no node in the tree falls within the given bounds.
3. Do the values for low and high follow any particular order?
   • Yes, it’s guaranteed that low ≤ high.

Strategy

1. Base Case:
   • If the root is null, return null.
2. Recursive Case:
   • If the value of the current node is less than low, then the entire left subtree of this node will also be out of range (because in a BST, all values in the left subtree are less than the node’s value). We, therefore, trim the left subtree and return the result of trimming the right subtree.
   • If the value of the current node is greater than high, then the entire right subtree of this node will also be out of range. We, therefore, trim the right subtree and return the result of trimming the left subtree.
   • If the value of the current node is within the range [low, high], we recursively trim both the left and right subtrees of the node.
3. The function should return the node itself in the last case after setting its left and right children to the trimmed subtrees.

Code

Here is the Java implementation based on the above strategy:

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. In the worst case, we need to visit every node to either discard it or include it in the trimmed tree.
• Space Complexity: O(h), where h is the height of the tree. In the worst case (for a skewed tree), it will require space proportional to the height of the tree due to the recursion stack.

This solution ensures that the resulting tree contains only nodes within the [low, high] range, preserving the structure of the BST.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?