The O(n) Club: Trim a Binary Search Tree—Because Even BSTs Need Spring Cleaning

The O(n) Club: Trim a Binary Search Tree—Because Even BSTs Need Spring Cleaning

⚡ TL;DR

You’ve got a BST and strict instructions: keep only the nodes whose values are between low and high. No, you don’t have to rebalance the survivors or attend their emotional support group. If a node’s value is too low, cut left and hoist up the right child. If it’s too high, lose the right and stick with the left. Use recursion and the BST rules to breeze through—no hand-waving.

// Java quick trim:
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;
}

🧠 How Devs Usually Mess This Up

Common rookie move: treating it like a generic tree. If you’re manually deleting nodes or rebuilding the tree from scratch, congratulations—you’re making it up as you go. Don’t trek through every node as if you’re checking their papers individually. And let’s not forget the inevitable slip-up: forgetting the BST property and missing out on huge speed boosts or flooding your code with null pointer exceptions you’ll regret at 2 AM.

🔍 What’s Actually Going On

Picture your BST as a velvet-roped club with an age restriction. Every parent only lets in someone—left child, younger than them; right child, older. If you find a kid who’s too young (< low), don’t bother peeking into their little siblings (left subtree)—they’re definitely not getting in. Too old (> high)? All their older siblings (right subtree) are out. When in range, you throw a recursive after-party for their left and right children, and everyone that makes it gets their place in the fancy, trimmed tree. No cheesy rebalancing, just BST purity.

🛠️ PseudoCode

• If node is null: You found a leaf’s ghost. Return null and move on.

  if (node == null) return null;

• If node.val < low: Kick everyone on the left out—recursively check the right child for salvation.

  if (node.val < low) return trimBST(node.right, low, high);

• If node.val > high: The right child and its descendants are out of range. Focus your trimming energies on the left child.

  if (node.val > high) return trimBST(node.left, low, high);

• Otherwise: This node survives! Apply trimming on both children, reconnect, and return your glorious survivor.

  node.left = trimBST(node.left, low, high);
  node.right = trimBST(node.right, low, high);
  return node;

💻 The Code

// Java: Trimming BST like a pro
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 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;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Nulls bite hard: Trimming creates fresh null branches. Take care before accessing children—unless you like NPEs with your coffee.
• It’s a BST, not a binary jungle: If you treat it like a plain tree, you’ll lose pruning elegance, speed, and possibly your sanity.
• Wild edge cases: The entire tree might be out of range—that’s fine, just return null. Lose the root? No big deal, new one is hand-picked for you by recursion.
• Time/space reality check: Each node gets one look: O(n) time, O(h) stack—no more, no less. Still faster than cleaning your desk.

🧠 Interviewer Brain-Tattoo

“Why recursion?” Because you’d rather be clever than tired—there’s no point checking every leaf if the BST is already telling you what’s not on the guest list. Remember: Even Marie Kondo couldn’t do this in better than O(n).