Algorithm

Sum Root to Leaf Numbers

Trees Pattern

Sum Root to Leaf Numbers

Every node of the tree holds a single digit from 0 to 9. Reading the digits along a root-to-leaf path from top to bottom spells out a decimal number — the path 4, 9, 5 spells 495. Return the sum of the numbers spelled by all root-to-leaf paths. A leaf is a node with no children; paths that stop at an internal node do not spell a number. The tree has at least one node, and the answer is guaranteed to fit in a 32-bit signed integer.

CONSTRAINTS
  • The number of nodes in the tree is in the range [1, 1000]
  • 0 <= Node.val <= 9
  • The tree depth will not exceed 10, so no number has more than 10 digits
  • The final sum fits in a 32-bit signed integer
EXAMPLE 1
Input: root = [1,2,3]
Output: 25
Two leaves give two numbers: the path 1, 2 spells 12 and the path 1, 3 spells 13. Their total is 25 — the digits are never summed individually, they are concatenated first.
EXAMPLE 2
Input: root = [4,9,0,5,1]
Output: 1026
Three leaves, three numbers: 495, 491 and 40. The shared prefix 4 is counted once per path, not once overall, because it is a digit of every number spelled below it.
EXAMPLE 3
Input: root = [0,1]
Output: 1
The single path spells 01, which is the number 1. A leading zero has no value, and the arithmetic handles that on its own without a special case.
EXAMPLE 4
Input: root = [7]
Output: 7
The root is itself a leaf, so it spells the one-digit number 7.
Are digits concatenated or added along a path?
Concatenated. The path 1, 2 gives 12, not 3, which is the entire difficulty separating this from Path Sum.
How should a leading zero be treated?
As nothing special — 0 then 1 spells 01, which is just 1. Building the number by repeated multiply-and-add produces this automatically.
Can the numbers overflow?
Not here: depth is capped at 10 and the total fits in 32 bits. Worth asking anyway, because an unbounded version would need a wider integer type.
Do paths ending at internal nodes count?
No. Only complete root-to-leaf paths spell a number, so a node with one child contributes nothing on its own.

Each root-to-leaf path spells a number by reading its digits top to bottom — 4, 9, 5 spells 495 — and we want the sum of all those numbers. The one thing to get right is that digits along a path are concatenated, not added: 4 then 9 is 49, not 13. Handle that cleanly and the rest is a short walk down the tree.

text
        4
       / \
      9   0
     / \
    5   1

  path 4-9-5 spells 495
  path 4-9-1 spells 491
  path 4-0   spells 40     ->   sum = 495 + 491 + 40 = 1026

Read the picture: each route from root to a leaf reads off as one number — the digits are glued together, not summed. The shared digit 4 at the top counts inside every number below it, which is why summing individual digits would give the wrong answer.

Growing a number one digit at a time

How do you turn the number 4 into 49? Not by adding 9 — that gives 13. The 4 has to move from the ones place into the tens place first, and in base 10 moving one place to the left is exactly multiplication by 10. So 4 becomes 40, and then the new digit slots into the vacated ones place: 40 + 9 = 49. Do it again with the digit 5: 49 × 10 = 490, plus 5 gives 495.

That is the whole mechanism, and it is one line:

text
number at this node = (number inherited from parent) × 10 + this node's digit

Two details fall out for free. Starting the root with an inherited value of 0 works, since 0 × 10 + 4 = 4. And a leading zero needs no special handling: from 0, the next digit gives 0 × 10 + 1 = 1, which is correct, because 01 simply is 1.

There is no need to build strings and parse them at the end. The digits arrive in exactly the order the arithmetic wants them — most significant first — so the number can be assembled on the way down as a plain integer.

Two directions in one function

Now, which way does information flow here? Both ways, and this problem is the clearest place to see them working together.

The number being built travels downward: a node's number depends entirely on the digits above it, so the parent computes it and passes it in as an argument, before making the recursive calls — that's the pre-order half. Meanwhile the total travels upward: a leaf reports the one number it spelled, and every internal node reports the sum of what its two subtrees reported back — that's the post-order half, combining children's answers on the way up. Same function, two channels: context handed down as a parameter, results handed up as a return value.

python
def total(node, built):
    if node is None:
        return 0                              # an absent subtree spells nothing, so adds 0
    built = built * 10 + node.val             # DOWN: extend the number for this node
    if node.left is None and node.right is None:
        return built                          # a leaf: hand back the one number it spelled
    return total(node.left, built) + total(node.right, built)   # UP: add what the sides reported

return total(root, 0)
Crucial Notethe null case returns 0 and the leaf case returns built, and these must stay separate. Suppose you delete the leaf test and simply return built whenever the node is null. Then a node with one child gets its number counted twice — once from the real child's subtree and once from the missing side — and a node with two children contributes nothing itself, which happens to be right for the wrong reason. Returning 0 for null works precisely because 0 is the identity for addition: an empty side changes no sum. Choosing base values that are identities for your combining operator is a habit worth keeping — it is 0 for sums, 1 for products, -infinity for maxima, and it removes most special cases before they appear.
Worked example:root 4, with children 9 and 0; 9 has children 5 and 1
- At 4, built = 0 × 10 + 4 = 4. Not a leaf, so both children are called with 4.
- At 9, built = 4 × 10 + 9 = 49. Not a leaf; both children called with 49.
- At 5, built = 49 × 10 + 5 = 495. A leaf — return 495.
- At 1, built = 49 × 10 + 1 = 491. A leaf — return 491.
- Node 9 adds its children's reports: 495 + 491 = 986, and returns that.
- At 0, built = 4 × 10 + 0 = 40. A leaf — return 40.
- The root adds 986 + 40 = 1026.

Follow the digit 4. It was never added to a total by itself; it was multiplied into every number spelled beneath it, three times over, once per leaf. That is why a shared prefix contributes repeatedly, and why summing the digits could never produce the right answer.

Cost, and the idea to keep

Each node is visited once and does constant work — one multiply, one add, one comparison — so O(N) time, with O(H) space for the recursion. No string ever gets built, no path list is stored; the only state in flight is a single integer per active call. Because the answer is one aggregate number rather than the routes themselves, there's never a reason to store the routes.

The idea to keep is the pairing: context down as a parameter, results up as a return value, in the same function. Once you can see both channels at once, a whole class of tree problems becomes mechanical — decide what each node inherits from above, decide what each node reports upward, and pick base values that are identities for the combining operator (0 for a sum, so an empty side changes nothing).

Interactive Strategy Visualization

Decimal Path Assembler

Digit-by-Digit Root Summation
49051
Assembly:
4
9
5
495
Mechanism Breakdown

Path 4 -> 9 -> 5 found. Digit concatenation: (4 * 100) + (9 * 10) + 5 = 495.

Grand Total
495
Sum of all root-to-leaf paths
Memory Rule
current = current * 10 + val

Strategy

Focus on the recursive nature of trees: solve for subtrees and combine results at the root.

"Divide and Conquer: Subproblem → Recurrence → Result"

O(N × H) Build Path Strings Then Parse
O(N) Time · O(H) Space Carry The Number Down