Remove BST keys outside given range

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Remove all BST nodes with values outside [min, max] range.

Algorithm

1Post-order: if node.val < min return trimBST(node.right, min, max). If > max return trimBST(node.left, min, max). Else recurse both sides.

Common Pitfalls

•Same as LC 669. Recursive trim: out-of-range nodes are replaced by their subtree that might be in range.

Remove BST keys outside given range.java

Java

// Approach: DFS. If node.val < min return pruned right subtree; if node.val > max return pruned left subtree.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    Node removekeys(Node root, int l, int r) {
        if (root == null)
            return null;

        if (root.data < l)
            return removekeys(root.right, l, r);

        if (root.data > r)
            return removekeys(root.left, l, r);

        root.left = removekeys(root.left, l, r);
        root.right = removekeys(root.right, l, r);
        return root;
    }
}

Was this solution helpful?