Free Trees lessonsTrees · Stage 3 · Paths · Step 3

Paths that start anywhere

Count the downward paths that add up to a target, starting at any node, by keeping the running sums of the ancestors in a map. About 20 minutes.

Running sums along the way down

A downward path that ends at the current node starts just below some ancestor, or at the root. Its sum is the running total at the current node minus the running total at that ancestor.

So the path sums to the target exactly when an ancestor had a running total equal to the current total minus the target. Count how many such ancestors there are with a lookup in a map of running totals.

Running total: sum from the root down to this node.

Look up: current total minus target.

In code

sums = [0, 3, 5, 9]
want = 9 - 4          # a total seen before
has = want in sums

Paths adding up to 6 in the tree 3, 2, 4, 1, 4, none, 2.

found: 1

At the 1 under 2, the totals along the way are 0, 3, 5, 6. Looking for 6 − 6 = 0: found once. The path 3, 2, 1 adds to 6.

Move 1 of 3

Add on the way in, remove on the way out

The map must hold only the running totals of the current node's ancestors, plus the empty prefix 0 so that paths starting at the root are counted. So add the current total before going to the children, and remove it after they return.

Without the removal, totals from a different branch would remain in the map, and would be counted as if they were ancestors. This add-then-undo pattern is called backtracking.

Start with total 0 seen once: for paths from the root.

Remove on the way out: or other branches leak in.

In code

path.append(node.val)    # step in
path.pop()               # step out: undo

Quick check

Why is the running total 0 placed in the map before the walk starts?

ASo that a path starting at the root itself is counted
BTo make the map faster
CIt is not needed

Show the answer

So that a path starting at the root itself is counted. Such a path's sum equals the current total minus 0.

Your problem

Path sum III

Given the root of a binary tree and an integer target, return the number of paths whose values add up to the target. A path may start and end at any node, but it must go downward, from a parent to a child, at every step.

Example

root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], target = 8 → 3

0 ≤ number of nodes ≤ 1,000 · -1,000 ≤ node.val ≤ 1,000 · -1,000,000 ≤ target ≤ 1,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.