Path Sum III Solution

Problem

Given a binary tree and a target number, count all downward-moving paths where the node values along the path sum exactly to the target. A path can start and end at any node — it does not need to begin at the root or stop at a leaf.

[10,5,-3,3,2,null,11,3,-2,null,1]

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Output: 3
Explanation: The three qualifying paths are 5→3, 5→2→1, and −3→11, each summing to 8.

Intuition

As you walk from the root to any node, you build a cumulative sum. Any contiguous downward subpath ending at the current node equals runningSum − someEarlierPrefix. If you've seen runningSum − targetSum as a prefix before, a valid path exists between that earlier node and the current one. Storing prefix sum frequencies in a hash map — and undoing entries as you backtrack — turns an O(n²) double-DFS into a clean O(n) pass.

Approach 1 — Brute Force Double DFS

For every node in the tree, launch a secondary DFS that tracks how much sum is still needed. The outer traversal picks starting nodes; the inner function walks downward from each one.

Define count_from(node, remaining): if the node's value equals remaining, record one path; always recurse down with remaining − node.val.
From each node, call count_from to count paths starting here.
Then recurse the outer function into the left and right subtrees to find paths starting deeper.
Return the total across all starting nodes.

1class Solution:
2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
3        def count_from(node: Optional[TreeNode], remaining: int) -> int:
4            if not node:
5                return 0
6            found = 1 if node.val == remaining else 0  # this node completes a valid path
7            found += count_from(node.left, remaining - node.val)
8            found += count_from(node.right, remaining - node.val)
9            return found
10
11        if not root:
12            return 0
13        # count paths starting here, then search for paths starting deeper in each subtree
14        return (count_from(root, targetSum)
15                + self.pathSum(root.left, targetSum)
16                + self.pathSum(root.right, targetSum))

Time: O(n²) in the worst case (a skewed tree) — the inner DFS is called once per node and can visit up to n nodes each time.
Space: O(n) — the recursion stack reaches depth n on a skewed tree.

Approach 2 — Prefix Sum with Hash Map

Maintain a running sum from the root to the current node. At each node, look up how many earlier nodes had a prefix sum equal to runningSum − targetSum; that count equals the number of valid paths ending here. A hash map tracks frequencies, and backtracking restores it before returning to the parent.

Initialize prefix_count = {0: 1} — the zero prefix exists once before the root, making root-to-node paths countable.
DFS through the tree, accumulating running_sum as you descend.
At each node, the answer contribution is prefix_count[running_sum − targetSum].
Record running_sum in the map, recurse into children, then decrement to backtrack.

1class Solution:
2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
3        prefix_count = {0: 1}  # zero prefix makes root-starting paths discoverable
4
5        def dfs(node: Optional[TreeNode], running_sum: int) -> int:
6            if not node:
7                return 0
8            running_sum += node.val
9            # earlier prefixes equal to (running_sum - targetSum) mark valid path starts
10            paths_found = prefix_count.get(running_sum - targetSum, 0)
11            prefix_count[running_sum] = prefix_count.get(running_sum, 0) + 1
12            paths_found += dfs(node.left, running_sum)
13            paths_found += dfs(node.right, running_sum)
14            prefix_count[running_sum] -= 1  # undo before returning so siblings see clean state
15            return paths_found
16
17        return dfs(root, 0)

Time: O(n) — each node is visited exactly once with O(1) hash map operations.
Space: O(n) — the map holds at most one entry per ancestor on the current root-to-node path, and the call stack also reaches depth n.

Complexity Summary

Approach	Time	Space	When to use
Brute Force Double DFS	O(n²)	O(n)	When the tree is small or you need to enumerate actual paths
Prefix Sum + Hash Map	O(n)	O(n)	Standard choice — same space cost, far better time

Common Mistakes

Omitting the {0: 1} seed: without this, paths that start at the root are never found — when you're at the root, runningSum − targetSum would need to match a prefix recorded before any traversal, and zero hasn't been registered yet.
Skipping the backtrack step: if you don't decrement prefix_count[running_sum] after returning from a node's children, those prefix sums persist and inflate counts in sibling subtrees that should not see them.
Confusing this with Path Sum II: Path Sum II requires paths from the root to a leaf; here any downward subpath qualifies, which is a fundamentally different (and harder) problem — an if-at-leaf check would silently miss most valid paths.
Integer overflow in the running sum: node values can be ±10⁹ and trees can have up to 1000 nodes; the accumulated sum overflows a 32-bit int, so Java and C++ solutions must use long for runningSum and the map key.
Calling the wrong recursive function in the brute force: when extending an in-progress path, you must call the inner count_from — accidentally calling pathSum restarts the search from that node as a new starting point, double-counting every descendant path.

Path Sum III — Solution