Path Sum III

Problem in plain words

Count the downward paths in a binary tree whose node values add up to a given targetSum. A path can start at any node and end at any node below it, but it must always move from parent to child. It does not have to touch the root or end at a leaf.

Example: root 4, left child 2, and 2 has a left child 2. With target 4, the paths 4 (just the root) and 2 → 2 both qualify, so the answer is 2.

Intuition

This is the tree version of "count subarrays with sum k". While walking down one root-to-node path, keep the running sum curr. A downward path ending at the current node sums to target exactly when some earlier prefix on the same path had sum curr - target. So keep a hash map from prefix sum to how many times it appears on the current path. Look up curr - target, add the count to the answer, then insert curr before going deeper. When you return from a node, remove its prefix — it is no longer on the path.

Approach

1. Create a map seen with seen[0] = 1 — the empty prefix, so paths starting at the root are counted.
2. DFS with the running sum. At each node add node.val to it.
3. Add seen[curr - target] to the answer.
4. Increment seen[curr], recurse into both children, then decrement seen[curr] (backtrack).
5. Return the accumulated count.

Dry run

Tree 4 → left 2 → left 2, target 4.

Total found = 2.

Java solution

class Solution {
    private final Map<Long, Integer> seen = new HashMap<>();
    private int target;

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        seen.put(0L, 1);
        return dfs(root, 0L);
    }

    private int dfs(TreeNode node, long running) {
        if (node == null) {
            return 0;
        }
        running += node.val;
        int found = seen.getOrDefault(running - target, 0);
        seen.merge(running, 1, Integer::sum);
        found += dfs(node.left, running) + dfs(node.right, running);
        seen.merge(running, -1, Integer::sum);
        return found;
    }
}

Python solution

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        seen = defaultdict(int)
        seen[0] = 1

        def dfs(node, running):
            if node is None:
                return 0
            running += node.val
            found = seen[running - targetSum]
            seen[running] += 1
            found += dfs(node.left, running) + dfs(node.right, running)
            seen[running] -= 1
            return found

        return dfs(root, 0)

Complexity

Edge cases and common mistakes

• Forgetting `seen[0] = 1` — without it, paths that start at the root are never counted.
• Integer overflow in Java — values up to 10^9 on a 1000-node path overflow int. Keep prefix sums in long.
• Skipping the backtrack step — if you do not remove curr when leaving a node, prefixes from a sibling branch leak in and produce false matches.
• Looking up after inserting — insert curr only after the lookup, otherwise a target of 0 would count the empty path.
• Empty tree — return 0.