Sum Root to Leaf Numbers

Medium#129top-down

You get the root of a binary tree whose nodes hold digits from 0 to 9. Each path from the root down to a leaf spells a number: 1 → 4 → 6 is 146. Return the sum of all these numbers. Our tree: 2 with children 7 and 5; 7 has children 3 and 0, and 5 has only a right child 8. The paths spell 273, 270, 258 — the answer is 801.

129 Sum Root to Leaf NumbersWalkthrough · 1×

Example: add up the numbers spelled by the root-to-leaf paths: each call appends its digit to the number it got from above and passes it on down.

275308leaf numbers—call stacktop on the right—
not visited yeton the path, waitingcurrent call, its number beside itreturned

Start at the root 2 with an empty number: walk(2, 0)

01/38
restart · back · play · step
Speed
1function sumNumbers(root):
2 return walk(root, 0)
3
4function walk(node, number):
5 number = number * 10 + node.val
6 if node.left is none and node.right is none:
7 return number
8 total = 0
9 for each child of node that is not none:
10 total = total + walk(child, number)
11 return total
state
root
2
node
–
number
–
total
–
click a step to go back

← → step · space play/pause

Why it works

  1. Appending a digit means number × 10 + val: the digits already there move one place left. So each node gets exactly the number spelled by the path above it, its own digit included.
  2. A number is complete only at a leaf, so only a leaf returns its number. An inner node such as 5 returns just what its children return, and 25 never gets into the sum.
  3. Each call returns the sum of the numbers in its subtree, so the root returns the sum of them all.

Complexity

Time O(n): each node is visited once. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.