Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Each root-to-leaf path spells a number, reading the node values as digits top to bottom. Carry that number down the recursion with the rule `current = current * 10 + node.val`, and at each leaf add the completed number to a running total. The base-10 shift is the whole idea: multiplying by 10 before adding the new digit appends it to the right.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you build the path number incrementally with the base-10 shift, finalize it only at leaves, and aggregate by summing across both subtrees rather than ORing or stopping early.
Where candidates slip
Adding the partial number to the total at internal nodes, or rebuilding numbers by concatenating strings and parsing at the end (works but is slower and signals you missed the arithmetic shift).
How to stand out
Articulate the `*10` shift as appending a digit, contrast the SUM aggregation here with the OR in Path Sum, and offer the iterative stack version carrying (node, partialNumber) pairs.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAt node: current = current*10 + valIs node null?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Recursive DFS Building the Number Downward
1Hint 1Explore hintHide hint
Think about what number the path to the current node spells so far. When you step into a child, how does that number change if the child is the next digit?
2Hint 2Explore hintHide hint
Appending a digit d to a number x is x * 10 + d. So pass the number-so-far into each recursive call and update it as current * 10 + node.val.
3Hint 3Explore hintHide hint
When you reach a leaf, the number is complete — return it. At internal nodes, return the SUM of what the left and right subtrees report, since every leaf contributes a separate number.
A · Core idea
The core realization is that the number a path spells can be built as you descend, one digit at a time, without ever storing the digits separately. We thread a parameter current through the recursion representing 'the number formed by the path from the root down to (and excluding) this node'. On entering a node we fold its digit in.
Why `current * 10 + node.val` appends a digit. In base 10, multiplying a number by 10 shifts every existing digit one place to the left and opens a units slot of value 0; adding the new digit fills that slot. So if the path so far spelled 12 and the next node is 3, then 12 * 10 + 3 = 123 — exactly the concatenation we want. This arithmetic is why we never need string building or parsing: the number is the accumulated state. Because every node value is guaranteed to be a single digit 0–9, the units slot is always filled by exactly one digit and the assembly is exact.
Why we finalize only at the leaf. A number is only complete when the path ends, and a path ends at a leaf. So the return value of a leaf is its fully-built current. At an internal node the number is still being formed — returning it there would count a prefix as if it were a whole number, which is wrong. The leaf guard node.left == null && node.right == null is the precise place where a partial number graduates into a final one.
Why we SUM the children instead of ORing them. This is the key contrast with Path Sum. There we asked 'does any path work?' and used OR with short-circuiting. Here we must total every root-to-leaf number, so an internal node returns dfs(left, current) + dfs(right, current). Each leaf in the subtree contributes its own number, and addition accumulates them all the way up to the root, which returns the grand total.
Why null contributes zero. A missing child represents no path and therefore no number, so it adds 0 to the sum. This matters for nodes with a single child: the present child returns its subtree's total, the absent child returns 0, and total + 0 correctly ignores the missing side. Crucially, the null case returns 0, not current — returning current would double-count the partial number once per missing child.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [4,9,0,5,1]Interactive diagram
The tree [4,9,0,5,1] and its three numbers
node 4, cur 0Three leaves spell 495, 491, and 40; their sum is 1026.
1026C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The number being formed is the recursion's downward state — there's no separate data structure. Seeing that *10 + digit turns 'concatenate a digit' into pure arithmetic is the same move that powers Decode Ways, Add Binary, and any digit-DP: represent a sequence as a number you grow incrementally.
ComplexityO(n) time, O(h) space — Each node is visited exactly once and does O(1) work, so time is O(n). Recursion depth equals the tree height h (≤ 10 here), giving O(h) stack space.
E · Edge cases and pitfalls7root = [0] — Single leaf with value 0 → current = 0 → returns 0. The only number is 0.Explore edge casesHide edge cases
Edge cases handled
root = [0]Single leaf with value 0 → current = 0 → returns 0. The only number is 0.root = [1,2]Node 1 has one child 2; the null right adds 0, the left leaf returns 12 → total 12. Confirms single-child handling.root = [1,0,0]Paths 10 and 10 → 10 + 10 = 20. Leading-then-zero digits assemble correctly via *10.
Pitfalls
- Returning current at internal nodes, counting partial prefixes as whole numbers.
- Returning current (not 0) from the null base case, double-counting on single-child nodes.
- Using OR/max across children instead of SUM — that solves a different problem.
- Building strings and parsing at the leaf — correct but slower and misses the arithmetic insight.
Approach 2 of 2 · Optimal
Iterative DFS with a Stack of (node, number) Pairs
1Hint 1Explore hintHide hint
The recursion's downward state is the number-so-far. To go iterative, store that number on the stack next to each node.
2Hint 2Explore hintHide hint
Push (node, numberAfterThisNode). When you pop a leaf, add its number to a running total.
3Hint 3Explore hintHide hint
For each non-leaf, push its non-null children with number = current * 10 + child.val.
A · Core idea
This converts the recursion to an explicit stack, the standard response to 'no recursion'. The state that recursion held in a parameter — the partial number — becomes part of each stack entry, paired with its node.
Why pair the number with the node. Recursion implicitly remembered, per frame, the number formed down to the current node. Removing recursion forces us to store that number ourselves. So each stack entry is (node, number) where number already includes node.val folded in via the *10 + val shift. When we pop the entry, the node's contribution is already accounted for.
Why the total accumulates at leaves only. We keep a separate running total. When a popped node is a leaf, its number is a finished root-to-leaf number, so we add it to total. Internal nodes don't touch total; they only push children with the extended number. This mirrors the recursive rule that finalization happens at leaves and aggregation is a sum.
Why we push children with the shifted number. For each existing child we push (child, number * 10 + child.val). The multiply-by-ten shift is identical to the recursive version — we're just doing it at push time instead of at call time. Null children are never pushed, which is how the iterative form encodes 'a missing path contributes nothing'.
Why complexity matches recursion. We visit each node once and the live stack never exceeds the current path depth, so the algorithm is O(n) time and O(h) space — the same as recursion, with the bookkeeping moved into our own container and immune to deep-recursion stack overflow.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3]Interactive diagram
How a path becomes a number
push rootDescending, each step shifts the running number left by one base-10 place and drops in the new digit.
25C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The recursion parameter (partial number) becomes a field of the stack tuple, and the 'sum across children' becomes a single shared accumulator updated at leaves. That 'parameter → tuple, aggregate → accumulator' translation is the universal recipe for de-recursing a tree DFS.
ComplexityO(n) time, O(h) space — Each node enters and leaves the stack once → O(n) time. The stack holds at most a root-to-leaf path's worth of frontier nodes → O(h) space.
E · Edge cases and pitfalls7root = [9] — Push (9,9); pop it, it's a leaf → total = 9.Explore edge casesHide edge cases
Edge cases handled
root = [9]Push (9,9); pop it, it's a leaf → total = 9.root = [1,2,3,4]Path 1→2→4 = 124 and 1→3 = 13 → total 137; demonstrates deeper number building.Tree of depth 10Numbers reach 10 digits but fit in int per constraints; iterative stack avoids recursion-depth concerns.
Pitfalls
- Adding to total at non-leaf pops, counting prefixes.
- Mismatching the two parallel stacks by pushing a node without its number.
- Pushing null children, then dereferencing them.
- Resetting total inside the loop instead of accumulating across all leaves.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int sumNumbers(TreeNode root) { if (root == null) return 0; Deque<TreeNode> nodes = new ArrayDeque<>(); Deque<Integer> numbers = new ArrayDeque<>(); nodes.push(root);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Summing at internal nodes
A number is only complete at a leaf. Adding current to a total at every node counts each prefix (e.g. 4, 49, 495) as if it were its own number.
Explore the code comparisonHide the code comparison
Summing at internal nodes
A number is only complete at a leaf. Adding current to a total at every node counts each prefix (e.g. 4, 49, 495) as if it were its own number.
Don't write this
private int dfs(TreeNode node, int current) {
if (node == null) return 0;
current = current * 10 + node.val;
total += current; // wrong: counts prefixes
return dfs(node.left, current) + dfs(node.right, current);
}Write this instead
private int dfs(TreeNode node, int current) {
if (node == null) return 0;
current = current * 10 + node.val;
if (node.left == null && node.right == null) return current;
return dfs(node.left, current) + dfs(node.right, current);
}2Null base case returns current instead of 0
On a node with one child, the missing side's recursive call should contribute 0. Returning current there adds the partial number an extra time, double-counting.
Explore the code comparisonHide the code comparison
Null base case returns current instead of 0
On a node with one child, the missing side's recursive call should contribute 0. Returning current there adds the partial number an extra time, double-counting.
Don't write this
def dfs(node, current):
current = current * 10 + node.val # crashes / wrong on None
if node is None:
return current # wrong: should be 0
...Write this instead
def dfs(node, current):
if node is None:
return 0
current = current * 10 + node.val
if node.left is None and node.right is None:
return current
return dfs(node.left, current) + dfs(node.right, current)3Forgetting the base-10 shift (string concat without parse)
Adding the digit without multiplying by ten (current + node.val) sums digits instead of concatenating them, producing 4+9+5 = 18 rather than 495.
Explore the code comparisonHide the code comparison
Forgetting the base-10 shift (string concat without parse)
Adding the digit without multiplying by ten (current + node.val) sums digits instead of concatenating them, producing 4+9+5 = 18 rather than 495.
Don't write this
current = current + node.val; // sums digits, not concatenationWrite this instead
current = current * 10 + node.val; // shifts then appends the digitRevise
Carry the pattern into the interview
Pattern to remember
Root-to-leaf DFS building a base-10 number by `*10 + digit`
Code pattern to memorize
dfs(node, current):
if node is null: return 0
current = current * 10 + node.val
if node is leaf: return current
return dfs(node.left, current) + dfs(node.right, current)Rules to remember
- 1Append a digit with
current = current * 10 + node.val— the multiply-by-ten shifts existing digits left. - 2Add to the total only at a leaf, where the number is complete — never at an internal node.
- 3A
nullnode contributes 0 to the sum, never the accumulatedcurrent. - 4Sum the two child results (left + right), unlike Path Sum which ORs them — every path contributes.
- 5Pass
currentdown as a parameter; don't try to reconstruct the number after the fact.
Use this pattern when
- Each root-to-leaf path encodes a value (digits, characters, a sequence) you must combine
- You need to aggregate over ALL paths, not just find one
- State for a path is built incrementally as you descend
- Digits are guaranteed 0–9, so base-10 assembly is exact
Choose another pattern when
- Only need whether one path hits a target → Path Sum (OR, not sum)
- Path can start/end anywhere → Path Sum III / Max Path Sum
- Need the list of numbers, not their sum → collect strings instead of accumulating
- Values aren't single digits → the *10 base-10 trick no longer applies cleanly
Interview takeaway
This is the root-to-leaf DFS template with a twist: instead of testing a sum you *construct* a number digit-by-digit. The `current * 10 + val` shift and 'finalize at the leaf, sum across children' pattern reappears anywhere a path encodes a sequence you must fold into a single value.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRoot-to-leaf DFS that constructs a value while descending. Recognise it when each path encodes a sequence (digits, bits, characters) you must fold into one number and aggregate across leaves. Swap the base (×10, ×2) or the aggregation (sum, min) and the same skeleton solves Sum of Root To Leaf Binary Numbers and Smallest String Starting From Leaf.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Path SumSame root-to-leaf DFS, but test for an exact target sum with OR instead of building a number.
- Binary Tree PathsComing soonCollect each root-to-leaf path as a string instead of folding it into a number.
- Smallest String Starting From LeafComing soonBuild a string down the path, but compare leaf-to-root order to find the lexicographically smallest.
- Sum of Root To Leaf Binary NumbersComing soonIdentical idea in base 2 — use current * 2 + node.val instead of *10.