437. Path Sum III

Medium · solved 2026-10-05 · Open on LeetCode

Bookmarked · Restudy this problem.

treebinary-treedfsprefix-sumhash-table

Time O(n) · Space O(h)

How to get there

A path is the difference of two running sums

1. Restate what is counted. Downward paths: they start at any node and end at any node below it, or at the start itself. Count those whose values add up to targetSum.

2. Count by hand and find the repeated work. The direct way, solution-1-original.py, starts a walk at every node and keeps a running sum on the way down. In LeetCode’s first example, 3 under 5 under 10 gets added again for every node above it that starts a walk. A node at depth d is re-added d times, so the total is O(n · h): O(n²) on a chain.

3. Reframe one path as a subtraction. Take the running sum from the root down to each node. For an ancestor A and a node X below it, the path from just under A down to X sums to running(X) − running(A). So a path ending at X sums to the target exactly when some ancestor’s running sum is running(X) − targetSum. It is subarray-sum-equals-k, applied to each root-to-node path.

4. Find what to remember. For each running sum, how many nodes on the current path have it: a hash map from sum to count. Seed it with {0: 1}, the sum before the root, so a path starting at the root itself is counted.

5. Keep branches apart. When the walk leaves a node, that node is no longer an ancestor of what comes next, so its running sum must come out of the map. Add it on the way down and remove it on the way back up, so the map always describes exactly the current root-to-node path.

6. Check the cost. Each node does one lookup and two updates: O(n) time. The map holds at most one entry per node on the current path, and the recursion is as deep as the tree: O(h) space.

The reusable recipe: to count stretches that sum to a target, look up running − target among the earlier running sums in a hash map. On a tree, add each sum on the way down and remove it on the way back, so the map follows the current path.

Let the map's meaning order the lines

Name	Always means, when `visit(node, running)` is entered
`running`	the sum from the root down to `node`’s parent; after `running += node.val`, down to `node` itself
`counts[s]`	how many of `node`’s ancestors, plus the empty start before the root, have running sum `s`
`visit(...)` returns	how many target paths end somewhere in `node`’s subtree

Code	What happened	What it keeps true
`counts = {0: 1}`	the walk hasn’t started	the sum before the root counts once, so paths can start at the root
`running += node.val`	the walk stepped down to `node`	`running` is the sum from the root to `node`
`found = counts.get(running - targetSum, 0)`	each ancestor with that sum starts one target path ending here	`found` counts the paths that end at `node`
`counts[running] = counts.get(running, 0) + 1`	`node` becomes an ancestor of everything below it	its children see its sum
`found += visit(node.left, running) + visit(node.right, running)`	both subtrees are counted	`found` covers the whole subtree
`counts[running] -= 1`	the walk leaves `node`	the map describes the current path again, so a sibling never sees this node’s sum

Why a count, not a set. Two nodes on one path can share a running sum when the stretch between them adds up to 0, and each of them starts its own path. On the tree [5, 3, 2, -3, null, null, null, 2] with target 2, the left branch runs 5 → 3 → −3 → 2, and since 3 + (−3) = 0 the running sum comes back to 5: the root and the −3 both have it. At the bottom 2, with running sum 7, the lookup is counts[5], which is 2: one path is 3 → −3 → 2 and the other is the 2 alone. Leaving the −3 then lowers counts[5] to 1, so the root’s right child, another 2, still finds the root’s 5 and counts itself. The answer is 3. A set that adds each sum and removes it on the way back finds only 1: it counts the shared 5 once, then deletes it when leaving the −3, although the root still holds it.

Why look up before adding. If node’s own sum were added first, a target of 0 would match it against itself and count an empty path. On the tree [0, 0, 0] with target 0, the order above finds the correct 5; adding first finds 8.

The method carries over: write down what the map describes, and every add has a matching remove at the point where that stops being true.

Alternatives compared

Approach	Time	Space	How it works
Walk down from every node (`solution-1-original.py`)	O(n · h)	O(h)	Each node starts its own walk with a running sum, counting every node where the sum hits the target.
Prefix sums in a hash map, recursive (chosen, `solution-2-prefix-sums.py`)	O(n)	O(h)	One walk from the root; each node looks up `running − targetSum` among its ancestors’ sums.
Prefix sums, iterative	O(n)	O(h)	The same walk with an explicit stack that also pushes an exit marker for each node, so its sum is removed after its subtree.

Measured locally on about 1,000 nodes, the problem’s limit: on a balanced tree the walk from every node took 1.6 ms and the prefix sums 0.4 ms; on a chain, 79.1 ms against 0.6 ms. The chain is where O(n · h) becomes O(n²).

The recursive version is one call per level, and a 1,000-node chain exceeds Python’s default limit of 1,000 calls: it raised RecursionError locally until the limit was raised. The iterative version has no such limit.

solution-1-original.py

# 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: TreeNode | None, targetSum: int) -> int:
        if not root:
            return 0

        root_stack, solution = [root], 0

        while root_stack:
            current_root = root_stack.pop()
            if current_root.right:
                root_stack.append(current_root.right)
            if current_root.left:
                root_stack.append(current_root.left)

            # stack tuple of tree node and sum from current root until current observer
            observer_stack = [(current_root, current_root.val)]

            while observer_stack:
                current_observer, observer_sum = observer_stack.pop()
                if observer_sum == targetSum:
                    solution += 1
                if current_observer.right:
                    sum = observer_sum+current_observer.right.val
                    observer_stack.append((current_observer.right, sum))
                if current_observer.left:
                    sum = observer_sum+current_observer.left.val
                    observer_stack.append((current_observer.left, sum))

        return solution

solution-2-prefix-sums.py

# 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: TreeNode | None, targetSum: int) -> int:
        counts = {0: 1}

        def visit(node: TreeNode | None, running: int) -> int:
            if not node:
                return 0
            running += node.val
            found = counts.get(running - targetSum, 0)
            counts[running] = counts.get(running, 0) + 1
            found += visit(node.left, running) + visit(node.right, running)
            counts[running] -= 1
            return found

        return visit(root, 0)

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.