Sum Root to Leaf Numbers: Building Numbers Top-Down

You are given the root of a binary tree containing digits 0 through 9. Each root-to-leaf path represents a number formed by concatenating the node values along the path. Return the total sum of all these root-to-leaf numbers.

This is LeetCode 129: Sum Root to Leaf Numbers. For example, the path 1 → 2 → 3 represents the number 123. If a tree has multiple root-to-leaf paths, you add up all the numbers they form.

Example 1: root = [1, 2, 3] produces paths 1 → 2 = 12 and 1 → 3 = 13. Output: 25.

Example 2: root = [4, 9, 0, 5, 1] produces paths 4 → 9 → 5 = 495, 4 → 9 → 1 = 491, and 4 → 0 = 40. Output: 1026.

The approach

The trick is to build each number as you walk down the tree, not after you reach the bottom. At each node, you take the number accumulated so far, multiply by 10, and add the current node's value. This is exactly how decimal digits work: shifting left by one place and appending the new digit.

When you reach a leaf, the accumulated number is complete. Return it. When you are at an internal node, recurse into both children and return the sum of their results.

This is a pre-order DFS where you pass current_num downward:

1. At each node: current_num = current_num * 10 + node.val
2. At a leaf (no children): return current_num
3. At an internal node: return dfs(left, current_num) + dfs(right, current_num)

The * 10 + val formula is the core insight. It mirrors how you would read a multi-digit number from left to right. The digit 4 becomes 49 when you append 9, then 495 when you append 5.

The solution

def sum_numbers(root):
    def dfs(node, current_num):
        if node is None:
            return 0
        current_num = current_num * 10 + node.val
        if node.left is None and node.right is None:
            return current_num
        return dfs(node.left, current_num) + dfs(node.right, current_num)

    return dfs(root, 0)

The outer function kicks off the DFS with current_num = 0. The inner dfs handles three cases:

• Null node: return 0. This handles the case where a node has only one child. The missing child contributes nothing.
• Leaf node: both children are None. The number is fully formed, so return current_num.
• Internal node: recurse into both children with the updated current_num. Sum their results.

Visual walkthrough

Let's trace through the tree [4, 9, 0, 5, 1] step by step. Watch how current_num grows as the DFS descends, and how leaf values bubble back up as sums.

The key observation: node 9 is not a leaf, so it does not return a number directly. Instead, it returns the sum of its two children (495 + 491 = 986). That sum flows back up to the root, which adds it to the right subtree's contribution (40) for the final answer of 1026.

Why * 10 + val works

Think about how you read the number 495 from its digits. You start with nothing (0). You see 4, so the number is 4. You see 9, so the number is 4 * 10 + 9 = 49. You see 5, so the number is 49 * 10 + 5 = 495.

This is Horner's method for evaluating a polynomial. Each step shifts the existing digits one place to the left (multiply by 10) and slots the new digit into the ones place (add val). It is the natural way to build a number digit by digit from left to right, which matches perfectly with a top-down tree traversal.

Complexity analysis

Time is O(n). You visit every node exactly once. Each visit does O(1) work (one multiplication and one addition).

Space is O(h) where h is the height of the tree. This is the maximum depth of the recursion call stack. For a balanced tree, h = log n. For a skewed tree (every node has only one child), h = n.

Edge cases to watch for

• Single node (root is a leaf): the tree has one path containing one digit. current_num = 0 * 10 + val = val. Return val directly.
• All left children (left-skewed tree): there is exactly one root-to-leaf path. The DFS follows it all the way down, building one number. The right child of every node is None, contributing 0 each time.
• All right children (right-skewed tree): same logic as all left children, just mirrored. One path, one number.
• Nodes with value 0: zeros are valid digits. The path 1 → 0 → 2 forms the number 102, not 12. The * 10 step ensures the zero occupies its proper place.

The building blocks

This problem is built on two fundamental building blocks:

Pre-order state passing. You pass current_num from parent to child during the recursive descent. At each node, you transform the state before passing it to children. The result is collected at the leaves. This is the same skeleton used in Path Sum (where the state is the remaining target) and Path Sum II (where the state is the current path list).

def solve(node, state):
    if node is None:
        return BASE
    state = TRANSFORM(state, node)
    if IS_LEAF(node):
        return state
    return COMBINE(solve(node.left, state), solve(node.right, state))

For this problem, TRANSFORM is state * 10 + node.val, and COMBINE is addition.

Digit accumulation. The current_num * 10 + digit formula builds a number from its most significant digit to its least. This pattern appears any time you need to reconstruct a number from a stream of digits, whether in a tree, a linked list, or an array.

From understanding to recall

You just watched current_num grow from 0 to 4 to 49 to 495 as the DFS descended through the tree. You saw how leaf values return directly and internal nodes sum their children's contributions. The * 10 + val formula makes intuitive sense right now.

But in an interview, will you remember to return 0 for null nodes (not current_num)? Will you remember that the leaf check requires both children to be None? Will you instinctively reach for pre-order state passing when you see a problem about accumulating values along root-to-leaf paths?

Understanding and recall are different skills. You understood the solution. Recall means producing it from scratch under pressure.

Spaced repetition builds recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the null base case, the leaf check, and the * 10 + val accumulation from scratch. After a few repetitions, the pattern is automatic.

Pre-order state passing and digit accumulation are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Path Sum - The foundational pre-order state passing problem. Instead of building a number going down, you subtract from a target. Same skeleton, different transform and combine operations.
• Binary Tree Maximum Path Sum - A harder tree problem where the path does not need to start at the root or end at a leaf. Good contrast for understanding when pre-order state passing applies and when it does not.