Pattern visualizer

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. 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]..

Binary Trees

step 1 / 11

Call stack

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

line 2

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap