The O(n) Club: Path Sum II: The Quest for Leafy Sums (or, Why Your Paths Keep Mutating)

The O(n) Club: Path Sum II – The Quest for Leafy Sums (or, Why Your Paths Keep Mutating)

⚡ TL;DR

Given a binary tree and a target sum, find all root-to-leaf paths where the node values add up to the target. Use DFS recursion, backtracking, and make sure to clone your path or Java will mess with your sanity.

// Brute force flavor:
void dfs(TreeNode node, int target, List<Integer> path) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null && sum(path) == target)
        result.add(new ArrayList<>(path)); // <-- copy is critical
    dfs(node.left, target, path);
    dfs(node.right, target, path);
    path.remove(path.size() - 1); // backtrack
}

🧠 How Devs Usually Mess This Up

Ah, classic dev moves:

• Partial Path Mania: Tossing in every possible path, regardless of whether it heroically reaches a leaf or just gives up halfway. Spoiler: root-to-leaf only, please.
• List Mutation Mayhem: Forget to make a copy before saving your path? Hope you like your answer mutating faster than your project requirements.
• Neglecting Negative Nodes: “I’ll prune branches when the sum is too big!” Nice try. Negative numbers mean yesterday’s impossible might come true with a little detour.

🔍 What’s Actually Going On

Picture your binary tree as a giant Choose Your Own Adventure, except every decision is made by a jittery dev on a caffeine bender. Traverse every possible story—every left and right branch—until you stumble out at a leaf. When you find a story (aka path) where all the choices add up to the target sum, you scribble down a copy. If the sum’s wrong, store nothing but resentment and backtrack.

Oh, and every time you record a path, clone it like production data before a big deploy. Java lists are drama queens: they’ll rewrite your results behind your back if you forget.

🛠️ PseudoCode

• Start at the root, DFS your way down.
  dfs(node, sumSoFar, pathSoFar)
• Add node value to sumSoFar and pathSoFar.
• If at a leaf:
  • If sumSoFar == target, record a copy of pathSoFar in result.
  • Otherwise, cry and backtrack.
• Recurse left and right.
• After both calls, remove last node from pathSoFar (backtrack).

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}
 class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), 0, result);
        return result;
    }
    private void dfs(TreeNode node, int target, List<Integer> path, int sum, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        sum += node.val;
        if (node.left == null && node.right == null && sum == target) {
            res.add(new ArrayList<>(path)); // Copy or die!
        }
        dfs(node.left, target, path, sum, res);
        dfs(node.right, target, path, sum, res);
        path.remove(path.size() - 1); // Backtrack
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Only root-to-leaf: Your cousin’s solution that checks inner paths? Not invited.
• Mutable list disaster: If you don’t copy at the leaf, your results will update every time you blink. Deep copy, friend.
• Negatives lurk below: Can’t stop on sum > target, because Mr. -1000 might be down the line.
• Time/Space: If N nodes, paths can be length N, so at worst O(N^2). Don’t worry, the tree won’t fit in your head anyway.

🧠 Interviewer Brain-Tattoo

“Lists are like post-it notes: if you don’t copy them, someone else will doodle right over your answer.”