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.
- 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
root = [1,2,3]25root = [4,9,0,5,1]1026root = [0,1]1root = [7]7Each 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.
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 = 1026Read 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.
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:
number at this node = (number inherited from parent) × 10 + this node's digitTwo 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.
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.
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)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.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.
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).
Decimal Path Assembler
Path 4 -> 9 -> 5 found. Digit concatenation: (4 * 100) + (9 * 10) + 5 = 495.
current = current * 10 + valStrategy
Focus on the recursive nature of trees: solve for subtrees and combine results at the root.
"Divide and Conquer: Subproblem → Recurrence → Result"