LC437 Path Sum III 🟡

A tough Path Sum upgrade — paths may start or end anywhere. We use DFS with a Prefix Sum notebook and Backtracking.

1. Problem Decoding

We have a Binary Tree whose nodes hold numbers (positive, negative, or zero) and a targetSum.
Count how many downward "paths" have node values that sum exactly to targetSum.

Three hard rules for counting paths:

1. Always go downward: parent → child/grandchild only (no climbing back up)
2. Start anywhere: does not have to begin at the Root
3. End anywhere: does not have to end at a Leaf

2. Mental Model

Picture the tree as a "hiking trail" and yourself as a "point collector" walking downhill. Recounting from every possible start is slow — so we keep a "prefix-sum notebook."

How the notebook works:

• As you walk downhill, always log the "Current Sum" from the summit
• Suppose targetSum is 8 and you've reached a Current Sum of 15
• Is there a stretch along the way that totals exactly 8?
• Instead of walking back to count, open the notebook and ask: "Have we ever logged a cumulative total of 7?"
• Why 7? Because 15 (current) − 8 (wanted) = 7 (past total)
• If 7 is in the notebook, the stretch from that past point to here added exactly 8 — that's one path we want

3. Logic-to-Code Mapping

Write dfs(node, current_sum) with a Hash Map as the notebook, plus Backtracking (erasing footprints).

Part 1: Prepare the notebook & fall off the edge

Seed the notebook with {0: 1} so paths that hit the target from the very start are covered.

# Notebook: key = prefix sum, value = how often we've seen it
prefix_map = {0: 1}

if not node:
    return 0  # fell off the edge — nothing to count

Part 2: Check the notebook (any path hitting Target?)

Update the current sum, then subtract the target to find the "past total" we need.

current_sum += node.val
old_sum = current_sum - targetSum

# If that past total is in the notebook, count those paths
paths = prefix_map.get(old_sum, 0)

Part 3: Log yourself, then go left & right

Record the current sum, recurse into both children, and add their path counts.

prefix_map[current_sum] = prefix_map.get(current_sum, 0) + 1

paths += dfs(node.left, current_sum)
paths += dfs(node.right, current_sum)

Part 4: Backtracking (erase the footprint — most important!)

Before climbing up to explore another branch, remove this node's prefix sum from the notebook so the right sibling never sees the left sibling's totals — that would break the "downward only" rule.

prefix_map[current_sum] -= 1
return paths

4. Step-by-Step Walkthrough

Tree: [10, 5, -3, 3, 2, null, 11] with targetSum = 8

      10
     /  \
    5   -3
   / \    \
  3   2    11

Start: notebook = {0: 1}

At node 10 (Root)

• Current Sum = 10
• Look up 10 − 8 = 2 in the notebook (miss → 0 paths)
• Log 10 → notebook becomes {0: 1, 10: 1}

Down left to node 5

• Current Sum = 10 + 5 = 15
• Look up 15 − 8 = 7 (miss → 0 paths)
• Log 15 → notebook becomes {0: 1, 10: 1, 15: 1}

Down left again to node 3

• Current Sum = 15 + 3 = 18
• Look up 18 − 8 = 10 (hit! once) → +1 path (nodes 5 → 3)
• Log 18 → notebook becomes {0: 1, 10: 1, 15: 1, 18: 1}

Backtrack out of node 3

• Can't go further — climb back to 5 and erase 18 from the notebook so the right child (node 2) never sees it

Continue through the rest of the tree to find the other paths (e.g. -3→11 and 5→2→1 in the full example) — total 3.

5. Full Assembled Code (Clean Code)

One shared prefix_map for the whole tree, with backtracking before climbing up:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:

        # Prefix Sum notebook
        prefix_map = {0: 1}

        def dfs(node, current_sum):
            if not node:
                return 0

            # 1. Add this node's points
            current_sum += node.val

            # 2. Have we seen (current − target) before?
            old_sum = current_sum - targetSum
            paths = prefix_map.get(old_sum, 0)

            # 3. Log the current sum (+1 frequency)
            prefix_map[current_sum] = prefix_map.get(current_sum, 0) + 1

            # 4. Explore left & right; accumulate path counts
            paths += dfs(node.left, current_sum)
            paths += dfs(node.right, current_sum)

            # 5. Backtracking: erase this node's footprint
            prefix_map[current_sum] -= 1

            return paths

        return dfs(root, 0)

6. Complexity Analysis

• Time Complexity: O(N) — one DFS visit per node; Hash Map ops average O(1)
• Space Complexity: O(N) — recursion stack up to O(H), and the map up to O(N) in the worst case (all distinct prefixes), so overall O(N)