437 · Path Sum III

The bridge from arrays to trees. This is the prefix-sum hash map from LC 560, Subarray Sum Equals K, transplanted onto the root path — with one addition the array version never needs: the map must be undone on the way up, or paths from different branches contaminate each other.

1 — The problem

Count paths summing to the target. Paths must go downward — parent to child — but need not start at the root or end at a leaf. Values may be negative.

The brute force is a nested traversal in the shape of LC 572: from every node, walk every downward path. O(n²), or O(n log n) on a balanced tree. It is accepted and it is not the answer.

1.1 The transfer from LC 560

On an array, "count subarrays summing to k" is solved by one pass keeping a map from prefix sum to how many times it has occurred. At index j with running sum S, the number of subarrays ending at j equals the number of earlier prefixes equal to S - k.

Everything transfers, because a root-to-node path is an array:

That last row is the only new idea, and it is forced by geometry. An array has one "before"; a tree node has one chain of ancestors, and a sibling in another branch has a different one. The map must describe the current root path and nothing else.

2 — One map, scoped to the current path

Target 8. Three paths qualify: 5→3, 5→2→1, and −3→11. Watch the seen strip — entries appear on the way down and disappear on the way up, so it never holds more than the current path's prefixes.

Notice the order inside the node: look up first, insert second. Inserting the current prefix before querying would let a node match itself whenever the target is 0 — a zero-length path, which is not a path.

2.1 What the undo prevents

Delete line 8 and the map accumulates every prefix ever seen, not just the ancestors'. Then a node can match a prefix from a cousin's branch — two nodes with no ancestor relationship — and the algorithm counts a "path" that is not connected at all.

In the tree above, both node 3 (left branch) and node 11 (right branch) produce a running sum of 18. Without the undo, 11's lookup would find the stale entry left by 3 and count a path running down one side of the tree and up the other. The answer inflates to 4.

2.2 Where else this transfer shows up

Once you see "the root path is an array", a family of array techniques becomes available on trees: sliding windows over a path, monotonic stacks along a spine, and any prefix-based aggregate. The reverse also holds — LC 1448 is "count elements that are a running maximum", a one-line array problem, given a tree's shape.

3 — Complexity and edge cases

• Time O(n) — one visit per node, O(1) expected map work. Space O(h) for the recursion and at most h + 1 live map entries.
• Target 0: legal, and the look-up-before-insert order is what keeps a node from counting itself as a zero-length path.
• Zero-valued nodes: produce duplicate prefix sums on one path, which is why the undo must decrement rather than remove.
• All negative values with a negative target: works — nothing here assumes monotonicity, unlike any pruning approach.
• Single node equal to the target: counted once, via the seeded 0.
• Common bug: forgetting line 8. The answer is too large, plausibly so, and only on trees where two branches share a prefix sum — so small tests pass.
• Common bug: inserting before querying. Only visible when the target is 0.

4 — Reference implementation

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> seen = new HashMap<>();
    seen.put(0L, 1);                       // paths that start at the root
    return dfs(root, 0L, targetSum, seen);
}

private int dfs(TreeNode nd, long run,
                int target, Map<Long, Integer> seen) {
    if (nd == null) return 0;
    run += nd.val;
    int c = seen.getOrDefault(run - target, 0);   // query BEFORE inserting
    seen.merge(run, 1, Integer::sum);
    c += dfs(nd.left,  run, target, seen);
    c += dfs(nd.right, run, target, seen);
    seen.merge(run, -1, Integer::sum);              // undo — scope the map to this path
    return c;
}

Lines 3–5 of the helper are LC 560 verbatim. Line 8 is the only thing the tree adds, and it is the same discipline as LC 257's path.remove — shared mutable state, undone on exit.