The O(n) Club: Path Sum III — Binary Tree Treasure Hunt for Grownups

The O(n) Club: Path Sum III — Binary Tree Treasure Hunt for Grownups

⚡ TL;DR

Count all downward (no climbing back up, sorry monkeys) paths in a binary tree that total a target sum. Start from any node, end wherever—if the sum hits the jackpot, it counts. Brute force is easy, but your time complexity will go rogue. Hash map with prefix sum is the real hero.

// Brute force, not for big-league trees
int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
 int dfs(TreeNode node, int sum) {
    if (node == null) return 0;
    int found = (node.val == sum) ? 1 : 0;
    return found + dfs(node.left, sum - node.val) + dfs(node.right, sum - node.val);
}

🧠 How Devs Usually Mess This Up

Let’s call it the “root tunnel vision” syndrome—devs think every path starts at the root and ends at a leaf. Instead, literally any node is fair game for the starting block. Oh, and if you write a DFS at every node, it’s like ordering a new coffee every 15 minutes: you feel busy but get nowhere fast. Expect your runtime to bloat faster than a holiday leftovers fridge.

• Not handling negative and zero values (yes, life can get negative—so can node values!)
• Forgetting that you can’t U-turn up a tree branch. Downward only. This is code, not a ski lift.
• Assuming child nodes never betray you by repeating values or reaching same sums in different ways.

🔍 What’s Actually Going On

Imagine you’re on a treasure hunt across a weird digital family tree. Each node is a tiny chest of coins (positive, negative or empty—welcome to disappointment!). The classic brute-force means starting a fresh hunt at each node, counting every valid path separately. Efficient? Only if your tree is smaller than your regrets.

Enter the prefix sum + hash map trick. You keep a running ‘loot tally’ as you wander down the tree. The hash map remembers how many times you’ve seen each tally so far. At each step, you check: have I seen a sum that, with my current total, makes up the target? Voila! Every such prefix marks a subpath from some ancestor to you, whose value is exactly the jackpot. Efficient, cool, and it makes you look smart in interviews.

🛠️ PseudoCode

• Carry along: current runningSum, a hash map (sum seen → count of ways)
• At each node:
  • Add node value to runningSum
  • If runningSum – target is in map: congrats! You found that many paths ending here
• Update hash: Increase count for runningSum
• Visit kids: Recursively process left/right kids with updated runningSum and hash map
• Cleanup: Backtrack by decrementing runningSum’s count (so siblings don’t cheat!)

void go(TreeNode node, int runSum, int target, Map<Integer,Integer> hash) {
  if (node == null) return;
  runSum += node.val;
  total += hash.getOrDefault(runSum - target, 0);
  hash.put(runSum, hash.getOrDefault(runSum, 0) + 1);
  go(node.left, runSum, target, hash);
  go(node.right, runSum, target, hash);
  hash.put(runSum, hash.get(runSum) - 1); // crucial!
}

💻 The Code

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> prefix = new HashMap<>();
        prefix.put(0, 1);
        return dfs(root, 0, targetSum, prefix);
    }
    private int dfs(TreeNode node, int runSum, int target, Map<Integer, Integer> prefix) {
        if (node == null) return 0;
        runSum += node.val;
        int count = prefix.getOrDefault(runSum - target, 0);
        prefix.put(runSum, prefix.getOrDefault(runSum, 0) + 1);
        count += dfs(node.left, runSum, target, prefix);
        count += dfs(node.right, runSum, target, prefix);
        prefix.put(runSum, prefix.get(runSum) - 1);
        return count;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgetting to decrease the hash map’s count after recursion—prepare for phantom paths and “ghost” bugs.
• Negative values: path sums swing both ways. Don’t assume they grow linearly.
• Never assume path must start at the root—reread the problem before embarrassing yourself in a whiteboard duel.
• Space: Hash map can be O(n) in the worst case (think unlucky all-zero tree). Stack is O(h) for recursion.

🧠 Interviewer Brain-Tattoo

“If you can solve it with an array trick, you can probably solve it with a vertical array. Trees: now with extra gravity.”