DSA Tracker

Visualize

Sum Root to Leaf Numbers

Appending a digit to a number shifts everything already there one place left: 49 followed by 5 is 49*10+5=495. So carry a running integer DOWN the recursion — multiply by 10 and add the node's digit at every step. A leaf hands that integer straight back up; an internal node just adds what its two children returned.

Details

Animated on: Each node holds a single digit. Return the sum of all numbers formed by concatenating digits along every root-to-leaf path, for the tree [4, 9, 0, 5, 1].

Problem:Sum Root to Leaf NumbersMedium

Binary Trees

step 1 / 11

5
9
1
4
0

Call stack

dfs(4, cur=0) -> cur=4

Enter node 4 with incoming total 0. New running total = 0 * 10 + 4 = 4. It has children, so recurse into both before it can return anything.

Pseudocode
1FUNCTION dfs(node, cur):
2  cur <- cur * 10 + node.val
3  IF node is leaf:
4    RETURN cur
5  ELSE:
6    RETURN dfs(node.left, cur) + dfs(node.right, cur)
7END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Enter node 4 with incoming total 0. New running total = 0 * 10 + 4 = 4. It has children, so recurse into both before it can return anything.
  2. Enter node 9 with incoming total 4. New running total = 4 * 10 + 9 = 49. It has children, so recurse into both before it can return anything.
  3. Node 5 is a leaf. Running total becomes 49 * 10 + 5 = 495 — that IS the number for this root-to-leaf path.
  4. dfs(5) returns 495 and pops off the stack.
  5. Node 1 is a leaf. Running total becomes 49 * 10 + 1 = 491 — that IS the number for this root-to-leaf path.
  6. dfs(1) returns 491 and pops off the stack.
  7. Both children of 9 are back: 495 + 491 = 986. dfs(9) returns 986.
  8. Node 0 is a leaf. Running total becomes 4 * 10 + 0 = 40 — that IS the number for this root-to-leaf path.
  9. dfs(0) returns 40 and pops off the stack.
  10. Both children of 4 are back: 986 + 40 = 1026. dfs(4) returns 1026.
  11. Answer = 1026: the three root-to-leaf numbers 495, 491 and 40 all summed exactly once, with no partial prefix counted.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sum Root to Leaf Numbers in the editorAll Binary Trees problemsBack to roadmap