Root-to-leaf path carry

35 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A tree holds numbers, and you are asked: is there a path from the top node down to some bottom node (a leaf) whose numbers add to 22? The tree: 5 at the top; 4 and 8 below; 11 under 4; 13 and 4 under 8; 7 and 2 under 11. By hand you would list every top-to-bottom path and add it up: 5+4+11+7 = 27, 5+4+11+2 = 22, found. That works, but it repeats the same additions: 5 + 4 + 11 is computed for both paths under 11, and in a big tree the shared prefix of thousands of paths is re-added thousands of times.

Build the structure, one piece at a time

The tree is unchanged. What we add is a small bundle of information that travels down the tree with the walk. Compare this with post-order folding, where answers travel up. Here the parent tells the child something before the child does anything.

Piece one: carry the "remaining target". Start at the root with 22. When you step onto a node, subtract its value. Hand the new remaining amount to each child. The child never needs to know the path above it; the single number stands in for the whole path.

Piece two: only leaves decide. A leaf checks: is the remaining amount, after subtracting me, exactly 0? If yes, a valid path exists. An inner node never decides; it only passes the state down and returns true if any child says true.

Piece three, generalising the bundle: for "sum of all root-to-leaf numbers" carry the number built so far, times 10 plus the digit at each step. For "print every path" carry the list of nodes so far and remove the last one when you come back up. For "count good nodes" carry the largest value seen so far on the path.

Why it is correct

The invariant: the state handed to a node describes exactly the path from the root to that node. At the root that is true (the state is the empty path, remaining 22). If it is true for a node, then subtracting the node's value gives a state that describes the path extended by that node, which is what each child receives. So it is true for every node.

remaining at a leaf = target − (sum of every value on the root-to-leaf path)

So "remaining = 0 at a leaf" is the same statement as "that path sums to the target". Checking only at leaves is required by the problem, which asks for root-to-leaf paths; an inner node reaching 0 is not an answer because the path must continue.

Why it is fast

Each node is stepped onto once and does one subtraction, so the time is O(n). The hand method re-added shared prefixes; here each value is added exactly once into the state that passes through it. Memory is the recursion depth, O(h). If the state is a growing list (for printing paths), copying it at every node would cost O(h) per node; push and pop on one shared list avoids that.

How to recognise it in an interview

Phrases like "root-to-leaf", "a path from the root", "the number formed by the digits along a path", "nodes that are the largest on their path". Say: "I will pass the accumulated state down the recursion and decide only at leaves." Path Sum carries the remaining target. Sum Root to Leaf Numbers carries the number built so far and adds it to a total at each leaf. Binary Tree Paths carries the string of the path and emits it at each leaf.

02The idea in one line

Pass accumulated state down; a leaf decides.

Reach for it when: Path sum, sum root-to-leaf numbers, binary tree paths, smallest string from leaf.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Path Sum 22 on [5,4,8,11,null,13,4,7,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pass the target down; subtract each node as you descend
2. At 5: remaining 22 − 5 = 17
3. At 4: remaining 17 − 4 = 13
4. At 11: remaining 13 − 11 = 2
5. At 7: remaining 2 − 7 = -5
6. Leaf 7 but remaining is -5, not 0: dead end
7. At 2: remaining 2 − 2 = 0
8. Leaf 2 with remaining 0: a path sums to 22
9. Path 5→4→11→2 = 22; every node visited at most once: O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.