Path Sum III: Prefix Sum in Trees

Given the root of a binary tree and an integer targetSum, return the number of paths where the values along the path sum to targetSum. The path does not need to start at the root or end at a leaf, but it must go downward (from parent to child nodes only).

This is LeetCode 437: Path Sum III, and it is a significant step up from Path Sum and Path Sum II. Those problems require root-to-leaf paths. This one lets paths start and end anywhere, as long as they go downward. That relaxation makes brute force expensive, and it opens the door to a beautiful technique: prefix sums on trees.

Why this problem matters

In Path Sum, you check whether one specific root-to-leaf path hits a target. In Path Sum II, you collect all such paths. Both problems constrain the path to start at the root and end at a leaf, which means you can carry a single running remainder from top to bottom.

Path Sum III removes both constraints. A valid path can start at any node and end at any descendant. If you try the naive approach of starting a fresh DFS from every node and checking all downward paths, you get O(n^2) time. That works for small trees, but it does not scale.

The prefix sum technique brings this down to O(n) by reusing a trick from the array world: if you know the cumulative sum at every point, you can find any subpath sum in constant time by subtracting two prefix sums. The same idea applies to paths in a tree.

The key insight

Think of the path from the root to any node as an array of values. The sum of any contiguous subpath within that array equals prefix_sum[end] - prefix_sum[start]. If that difference equals targetSum, you have found a valid path.

In concrete terms: as you DFS through the tree, maintain a running current_sum that accumulates node values from the root. At each node, check how many previously seen prefix sums equal current_sum - targetSum. Each one represents the start of a valid path that ends at the current node.

You store these prefix sums in a hash map (a counter). The key is the prefix sum value, and the value is how many times you have seen it on the current root-to-node path.

For the tree above with target 8:

• At node 10: current_sum = 10. Check 10 - 8 = 2. Not in map. No path.
• At node 5: current_sum = 15. Check 15 - 8 = 7. Not in map. No path.
• At node 3: current_sum = 18. Check 18 - 8 = 10. The value 10 is in the map (from the root). That means the subpath from after node 10 to node 3 sums to 8. Path found: [5, 3].
• At node 2 (child of 5): current_sum = 17. Check 17 - 8 = 9. Not in map.
• At node 1 (child of 2): current_sum = 18. Check 18 - 8 = 10. The value 10 is in the map again. Path found: [5, 2, 1].
• At node -3: current_sum = 7. Check 7 - 8 = -1. Not in map.
• At node 11: current_sum = 18. Check 18 - 8 = 10. The value 10 is in the map. Path found: [-3, 11].

The crucial detail: you seed the map with {0: 1} before starting. This handles paths that start at the root, where current_sum - targetSum = 0.

The solution

def path_sum(root, target_sum):
    count = 0
    prefix_map = {0: 1}

    def dfs(node, current_sum):
        nonlocal count
        if node is None:
            return
        current_sum += node.val
        count += prefix_map.get(current_sum - target_sum, 0)
        prefix_map[current_sum] = prefix_map.get(current_sum, 0) + 1
        dfs(node.left, current_sum)
        dfs(node.right, current_sum)
        prefix_map[current_sum] -= 1

    dfs(root, 0)
    return count

Let's break this down line by line:

• count = 0 tracks the total number of valid paths found across the entire tree.
• prefix_map = {0: 1} seeds the map with a prefix sum of 0 appearing once. This ensures that if current_sum itself equals target_sum at any node, you count the path from the root to that node.
• current_sum += node.val accumulates the running sum from the root to the current node.
• count += prefix_map.get(current_sum - target_sum, 0) is the core lookup. If current_sum - target_sum exists in the map, it means there is some ancestor where the prefix sum was exactly current_sum - target_sum. The path from just below that ancestor to the current node sums to target_sum.
• prefix_map[current_sum] = prefix_map.get(current_sum, 0) + 1 records the current prefix sum in the map before recursing into children.
• The two recursive calls explore both subtrees.
• prefix_map[current_sum] -= 1 is the backtracking step. When you return from a node, you remove its prefix sum from the map so it does not affect nodes in other branches. This is essential because the prefix sum map must only contain sums along the current root-to-node path.

Visual walkthrough

Let's trace the prefix sum DFS through the tree with target 8. Watch how the prefix map grows and shrinks as you traverse and backtrack, and how the lookup current_sum - target finds valid paths.

The key moments are Steps 3, 6, and 8. In each case, current_sum - target_sum produces a value that already exists in the prefix map. That match means a contiguous downward path ending at the current node sums to exactly 8. Notice how the map shrinks during backtracking (Step 5 and Step 7), ensuring that prefix sums from one branch never interfere with another.

Complexity analysis

Time is O(n). You visit every node exactly once. At each node, the hash map lookup and update are O(1). No node is visited more than once because the DFS does not restart from intermediate nodes.

Space is O(n) in the worst case. The prefix map can hold up to O(h) entries at any time (one per node on the current root-to-node path), where h is the height. The recursion stack also uses O(h) space. For a balanced tree, h = log n. For a completely skewed tree (like a linked list), h = n.

Compared to the brute force approach of starting a DFS from every node (O(n^2) time), the prefix sum technique is a major improvement for large trees.

Edge cases to watch for

• Empty tree (root is None): return 0. There are no paths at all.
• Single node equals target: the root has value equal to targetSum. The prefix map is seeded with {0: 1}, so current_sum - target_sum = 0 is found in the map. Returns 1.
• Negative node values: prefix sums naturally handle negatives. A running sum can decrease, and current_sum - target_sum still correctly identifies valid subpaths.
• Target sum is 0: valid paths are subpaths where the values cancel out. The prefix sum approach handles this without any special logic.
• Overlapping paths: multiple paths can share nodes. For example, both [5, 3] and [5, 2, 1] in the example share node 5. The prefix map counts all valid starting points independently.
• Duplicate prefix sums: if two ancestors have the same prefix sum, the map stores a count greater than 1, correctly counting multiple valid paths ending at the current node.

The building blocks

This problem combines two fundamental building blocks:

Prefix sum with hash map. You maintain a running cumulative sum and a hash map of previously seen prefix sums. To find how many subpaths ending at the current position sum to the target, you look up current_sum - target in the map. This is the same technique used in Subarray Sum Equals K, and it reduces a nested-loop problem to a single-pass solution.

def count_subarray_sum(nums, target):
    count = 0
    prefix_map = {0: 1}
    current = 0
    for num in nums:
        current += num
        count += prefix_map.get(current - target, 0)
        prefix_map[current] = prefix_map.get(current, 0) + 1
    return count

DFS with backtracking on shared state. You carry a mutable data structure (the prefix map) through the DFS. Before recursing into children, you add to it. After returning from the subtree, you undo your addition. This ensures the shared state only reflects the current root-to-node path. The skeleton looks like this:

def dfs(node, state):
    if node is None:
        return
    ADD_TO_STATE(state, node)
    PROCESS(node, state)
    dfs(node.left, state)
    dfs(node.right, state)
    REMOVE_FROM_STATE(state, node)

Together, these two blocks turn an O(n^2) problem into an elegant O(n) solution. If you can write the prefix sum pattern from memory and know to backtrack on the shared map, Path Sum III becomes clean and concise.

From understanding to recall

You just traced through a prefix sum DFS that counts every downward path summing to 8. You saw how the hash map lookup replaces brute-force enumeration, and how backtracking keeps the map honest across branches. The technique makes sense right now.

But will you remember to seed the map with {0: 1}? Will you remember that the decrement step after recursion is not optional? These small details are the difference between a clean solution and a debugging session under interview pressure.

Spaced repetition builds recall for exactly these details. You type the solution from scratch after a day, then three days, then a week. Each repetition forces you to reconstruct the prefix map initialization, the lookup, the increment, and the decrement. After a few rounds, the prefix sum on trees pattern is automatic.

Prefix sum with hash map and DFS with backtracking are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Path Sum - The boolean root-to-leaf version. Same tree traversal, but constrained paths and a simpler technique. Start here if you have not solved it yet.
• Path Sum II - Collects all root-to-leaf paths that match a target. Introduces backtracking with path tracking.
• Binary Tree Maximum Path Sum - Finds the maximum sum path that can go through any node. A different flavor of tree path problems that uses post-order returns instead of prefix sums.