LeetCode #129 Medium

Sum Root to Leaf Numbers

Each root-to-leaf path spells a number; return the sum of all such numbers.

treedfsrecursion

02

Intuition

Summing digit values as you go, or building a string along the path and parsing it at the leaf, both technically work but miss the clean trick: carry the number itself down the recursion with cur = cur * 10 + node.val. The multiply-by-10 IS the place-value shift that a string concatenation is imitating the hard way. Only add cur to the running total when you hit an actual leaf -- adding at every node would count partial paths that were never meant to be numbers.

How to spot this pattern

Carry the running number down as a parameter, building it with cur * 10 + node.val. Adding to the total only at leaves is what makes each complete root-to-leaf path count exactly once — internal nodes contribute nothing on their own.

03

Approach

1

Carry the running number down

At each node, cur = cur * 10 + node.val -- this is the number formed by the path from the root to this node, kept correct at every depth without any string work.

2

Only total at leaves

If a node has no left and no right child, add cur to the running total -- it is a complete root-to-leaf number.

3

Recurse both sides with the updated cur

Pass the new cur value into both children; each subtree continues extending its own copy of the path number independently.

04

Solution & live demo

▶1class Solution:
▶2    def sumNumbers(self, root):
▶3        total = 0
▶4 
▶5        def dfs(node, cur):
▶6            nonlocal total
▶7            if not node:
▶8                return
▶9            cur = cur * 10 + node.val
▶10            if not node.left and not node.right:
▶11                total += cur
▶12                return
▶13            dfs(node.left, cur)
▶14            dfs(node.right, cur)
▶15 
▶16        dfs(root, 0)
▶17        return total

05

Common pitfalls

Adding at every node

✗ Wrong

total += cur

✓ Right

if not node.left and not node.right:
    total += cur

Only complete paths ending at a leaf form a number. Accumulating at internal nodes adds every prefix — 1, 12, 123 instead of just 123.

Building the number with string concatenation

✗ Wrong

cur = cur + str(node.val)
total += int(cur)

✓ Right

cur = cur * 10 + node.val

Allocates a string per node and parses it at every leaf. The arithmetic form is one multiply-add and never leaves integer space.

Mutating a shared running value

✗ Wrong

self.cur = self.cur * 10 + node.val
dfs(node.left); dfs(node.right)

✓ Right

dfs(node.left, cur)
dfs(node.right, cur)

A shared field carries the left subtree's digits into the right subtree unless explicitly undone on the way back up. Passing cur as a parameter gives each branch its own copy for free.

06

Edge cases

Empty tree

Return 0, no paths exist.

Single node

That node is itself both root and leaf; its value is the sum.

Root value 0

cur starts at 0*10+0=0, still correct -- leading zero paths are fine since LeetCode guarantees no path represents a number with a leading zero beyond the root itself.

Deep skewed tree

cur grows correctly at each level via the *10 shift regardless of tree shape.

07

Complexity

Time

O(n)

Space

O(h)

Each node visited once; recursion stack bounded by tree height.