Top-Down State and Path Prefix Sums (the Traveler)

In the top-down style the parent passes data down to its children. Think of the recursion as a traveler carrying a backpack: the running sum, the path so far, the allowed range, the smallest and largest value seen. Use it whenever a node's answer depends on the path from the root to that node, not on its subtree.

The idea#

The state for a child is the parent's state plus the parent itself: dfs(node.left, curr_sum + node.val). Nothing comes back up except, perhaps, a global count. Each node is visited once, so the walk is $O(n)$ as long as updating the state is $O(1)$ .

The most useful version of this pattern is prefix sums on a tree path. It carries the array trick for subarray sums over to trees. A downward path from an ancestor a to a node x sums to prefix(x) - prefix(a), exactly as for a subarray. So at each node, the number of downward paths ending here with sum target is the number of ancestors whose prefix equals curr - target. A hashmap of prefix counts answers that in $O(1)$ .

There is one catch, and it is easy to miss. The map must hold only the prefixes on the current root-to-node path. When the walk returns from a node, that node stops being an ancestor of whatever is visited next (its sibling's subtree). So you decrement its prefix on the way out. Without that, a node in the right subtree would pair with a prefix from the left subtree and count a "path" that doesn't exist.

How to spot it#

Look for an answer that depends on what lies above the node.

"Root-to-leaf", "path from the root", "ancestor".
A constraint that narrows as you go down: a valid BST range, a running min and max.
"Count paths that sum to k" where paths go downward but may start anywhere.
"Good nodes": nothing on the path above is larger.

Template#

This is the plain traveler. The state rides down as an argument. Nodes follow LeetCode's TreeNode(val, left, right).

walk(node, state):
    if node is None: return
    check node against state; update the answer
    child_state = state updated with node     # sum, range, min/max, path
    walk(node.left, child_state)
    walk(node.right, child_state)
walk(root, starting state)

Prefix sums on a path#

The counting version from "The idea" keeps the same walk. It adds a map of prefix counts and undoes each entry on the way out.

prefix = map of counts, with prefix[0] = 1   # a path may start at the root
walk(node, curr):
    if node is None: return
    curr += node.val
    count += prefix[curr - target]          # ancestors that start a path
    prefix[curr] += 1
    walk(node.left, curr)
    walk(node.right, curr)
    prefix[curr] -= 1                        # leaving: no longer an ancestor

Brute force for comparison#

To see why the map is worth the extra lines, compare it with the obvious approach: start a fresh "sum from here" walk at every node. That is $O(n^2)$ on a skewed tree. The prefix map gives $O(n)$ .

Pitfalls#

These mistakes over-count or share state by accident.

Forgetting to undo the prefix count. This is the easiest bug to make in the whole pattern: prefix[curr] -= 1 on the way out. Without it, sibling subtrees see each other's prefixes and you over-count.
The shared-reference bug. If you pass a mutable path list down and append to it, every branch shares one list. Pass a copy (path + [node.val]), or append, recurse and path.pop().
Pruning on a negative tree. Stopping when curr_sum > target looks safe, but if values can be negative the sum may come back down. You can't prune early.
Seeding the map. Without prefix[0] = 1, paths that start at the root are missed.
Checking only the parent. A constraint set high up still applies deep down, so carry it all the way.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Path Sum

Carry (node, curr_sum) and compare with the target only at a leaf. A BFS queue of (node, curr_sum) also works and can return as soon as one leaf matches.

Hint: Path Sum II

Also carry the path, and copy it into the answer at a matching leaf. Watch the shared-reference bug: pass a copy, or append, recurse and pop.

Hint: Sum Root to Leaf Numbers

Carry the number itself: the child gets num * 10 + node.val. That is simpler than collecting digit strings. An empty tree sums to 0.

Hint: Validate Binary Search Tree

Carry the range a node may sit in. The root gets (-inf, +inf), a left child (lo, node.val) and a right child (node.val, hi). A deep node can satisfy its parent and still break a rule set higher up. An inorder walk that stays strictly increasing also works.

Hint: Maximum Difference Between Node and Ancestor

Carry the min and max seen on the path. At each node, the best difference is the larger of abs(node.val - lo) and abs(node.val - hi). Start both at root.val.

Hint: Longest ZigZag Path in a Binary Tree

Carry the direction you may take next and the current length. Going the allowed way extends the zigzag (length + 1). Going the other way restarts it at length 1, because that child begins a fresh zigzag. Record the maximum at every node.

Hint: Count Good Nodes in Binary Tree

Carry the largest value on the path above. A node is good when its value is at least that maximum. Pass the larger of the two down.

Hint: Path Sum III

Use the prefix-sum shape. Seed prefix[0] = 1, and decrement the count when you leave a node.

Key takeaways#

Top-down means the parent passes state to its children as arguments.
Use it when the answer depends on the path from the root, not on the subtree.
Downward path sums are prefix differences, so a hashmap of prefix counts works on trees.
Undo the prefix count when you leave a node; the map holds only the current path.
Never share a mutable path between branches, and never prune early when values can be negative.

Core idea#

In the top-down style, the parent passes state down to its children as arguments. Use it when a node's answer depends on the path from the root, not on its subtree.

Key points#

The child's state is the parent's state plus the parent: dfs(node.left, curr + node.val).
With $O(1)$ state updates, the walk is $O(n)$ .
A downward path from ancestor a to node x sums to prefix(x) - prefix(a).
Count paths ending here with prefix[curr - target].
The map holds only the current root-to-node path. Decrement the prefix on the way out.
Validate a BST with a range: root (-inf, inf), left (lo, node.val), right (node.val, hi).
Sum Root to Leaf Numbers: pass num * 10 + node.val.
Longest ZigZag: go the allowed way and extend, or go the other way and restart at 1.
Spot it: root-to-leaf, ancestor, a narrowing range, good nodes, count paths that sum to k.

Template#

prefix = map of counts, with prefix[0] = 1   # path may start at root
walk(node, curr):
    if node is None: return
    curr += node.val
    count += prefix[curr - target]
    prefix[curr] += 1
    walk(node.left, curr)
    walk(node.right, curr)
    prefix[curr] -= 1                        # no longer an ancestor

Pitfalls#

No undo of the prefix count. Sibling subtrees see each other's prefixes and you over-count.
A shared mutable path. Pass path + [node.val], or append, recurse and path.pop().
Early pruning when values can be negative. The sum can come back down.
No prefix[0] = 1. Paths that start at the root are missed.

Say it in an interview#

"The answer depends on the path above, so pass state down."
"A prefix-sum map gives O(n). Undo each prefix when you leave the node."