The O(n) Club: Range Sum of BST — Prune or Perish Edition

The O(n) Club: Range Sum of BST — Prune or Perish Edition

⚡ TL;DR

You’re told to sum BST node values within [low, high]. If you brute force every node, your interviewer weeps. Instead, skip useless branches with pruning:

// Brute-force Java (not cool)
int rangeSumBST(TreeNode root, int low, int high) {
    if (root == null) return 0;
    int left = rangeSumBST(root.left, low, high);
    int right = rangeSumBST(root.right, low, high);
    return ((root.val >= low && root.val <= high) ? root.val : 0) + left + right;
}

🧠 How Devs Usually Mess This Up

Most devs wander through the whole tree, visiting every single node, even if it’s painfully obvious half of them are out of range. It’s like checking every aisle for coffee when you’re standing in the produce section. Also, everyone loves to forget inclusivity: leave out those exact low and high values, and your test case #7 is toast.

🔍 What’s Actually Going On

BSTs are picky about order: everything left is smaller, everything right is bigger. If your current node is too small (< low), skip left; if it’s too big (> high), skip right. This isn’t just a time-saver—it’s a sanity-saver for large trees. Pruning is your best friend since college group projects.

🛠️ PseudoCode

• If node is null:

  return 0;

  Null nodes have no value. Ignore the ghosts.
• If node.val < low:

  return recurse on right;

  Left is full of even smaller stuff. Move along.
• If node.val > high:

  return recurse on left;

  Right is off-limits, bigger than your dreams.
• Else (in range):

  return node.val + recurse left + recurse right;

  Congrats, this one’s in. Take the money and run.

💻 The Code

// TreeNode definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low) {
            // Only right kids might fit
            return rangeSumBST(root.right, low, high);
        }
        if (root.val > high) {
            // Only left kids might fit
            return rangeSumBST(root.left, low, high);
        }
        return root.val
            + rangeSumBST(root.left, low, high)
            + rangeSumBST(root.right, low, high);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Inclusivity fail: Don’t skip the == low and == high checks—the interval is inclusive.
• Missed pruning: If you’re hitting every node, congrats on writing a basic DFS; that’s not O(height), and that’s not clever.
• Stack overflows: BST height can reach 20,000. Unbalanced trees push Java’s recursion limit. Just a friendly reminder.
• Null pointer pain: Recurse on null? That’s a stack trace, not a sum.
• Complexity: Time is O(N) worst case, O(H) space for stack. Pruning well means you visit far fewer nodes in balanced trees.

🧠 Interviewer Brain-Tattoo

Don’t do more work than you should—unless you also alphabetize your groceries. Prune what doesn’t matter: code, trees, even your browser tabs.