Sum of Root-to-Leaf Numbers, in depth: Horner's rule on a tree, recursive, stack, BFS and O(1)-space Morris solutions, variants and pitfalls

First principles: reading a path as a number

How does a computer turn the string "495" into the integer 495? It starts at zero and, for each digit, multiplies the running value by ten and adds the digit: 0 to 4, 4 to 49, 49 to 495. That is Horner's rule for evaluating a polynomial in base ten, and it has one crucial property: it needs only the running value, not the digits seen so far.

A root-to-leaf path is exactly such a string, read top-down. So each node can compute its own prefix value as acc = parent_acc * 10 + node.val and pass it to its children. When a node has no children, the prefix value is a complete number and becomes one term of the answer. Internal nodes contribute nothing directly; their digits are already inside every number below them.

There is a second, equivalent view that is useful for reasoning. A node at depth d (root at depth 0) contributes its digit multiplied by 10 to the power of (leaf depth minus d), once for each leaf in its subtree. That shows why a digit near the root matters far more than a digit near the leaves, and why the problem cannot be solved by summing node values: the same digit is worth different amounts on different paths.

Worked example

Trace the tree [4,9,0,5,1] by hand. The root gives acc = 4. Going left, 9 gives 4 * 10 + 9 = 49; its children give 495 and 491, both leaves. Going right from the root, 0 gives 40, also a leaf. The total is 495 + 491 + 40 = 1026. Note that the zero is a perfectly good digit: it multiplies the prefix by ten and adds nothing. A leading zero is harmless too, because a path 0 then 7 yields 0 * 10 + 7 = 7, which is how the integer "07" would parse.

The recursive solution

The recursive solution writes the idea down almost word for word. Pass the prefix value as an argument, return the sum of complete numbers in the subtree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def sum_numbers(root):
    def dfs(node, acc):
        if node is None:
            return 0                          # an empty subtree holds no numbers
        acc = acc * 10 + node.val
        if node.left is None and node.right is None:
            return acc                        # a leaf completes one number
        return dfs(node.left, acc) + dfs(node.right, acc)
    return dfs(root, 0)

Each node is visited once and does constant work, so time is O(n) for n nodes. Extra space is the recursion depth, O(h) for height h: O(log n) for a balanced tree and O(n) for a degenerate chain. The empty tree returns 0, which is the natural sum of no numbers.

The two base cases do different jobs and must not be merged. The null case answers "how many numbers are below a missing child?" with zero. The leaf case is where a number is actually emitted. The most common bug, covered below, comes from collapsing them.

Iterative versions: stack and queue

Python's default recursion limit is 1,000 frames, and other languages have fixed stack sizes, so a deep chain-shaped tree can crash the recursive version. An explicit stack of (node, prefix) pairs removes that risk with identical logic. This is the general recipe described in iterative DFS with an explicit stack.

def sum_numbers_stack(root):
    if root is None:
        return 0
    total, stack = 0, [(root, 0)]
    while stack:
        node, acc = stack.pop()
        acc = acc * 10 + node.val
        if node.left is None and node.right is None:
            total += acc
            continue
        if node.right:
            stack.append((node.right, acc))
        if node.left:
            stack.append((node.left, acc))
    return total

Because each stack entry carries its own prefix, there is nothing to undo when a branch finishes. That is the advantage over the backtracking style used in backtracking, where one shared path list is extended and then popped. Integers are immutable and cheap to copy, so passing them by value is both simpler and safer.

A queue gives a level-order version. It finds the same leaves in a different order and uses O(w) space for maximum width w, which is worse for bushy trees and better for tall thin ones.

from collections import deque

def sum_numbers_bfs(root):
    if root is None:
        return 0
    total, queue = 0, deque([(root, root.val)])
    while queue:
        node, acc = queue.popleft()
        if node.left is None and node.right is None:
            total += acc
        for child in (node.left, node.right):
            if child:
                queue.append((child, acc * 10 + child.val))
    return total

Constant extra space with Morris traversal

Can the problem be solved with O(1) extra space? Yes, using Morris traversal, which temporarily rewires null right pointers into threads back to an ancestor and removes them on the second visit. The Morris in-order traversal article explains the threading itself. The extra difficulty here is that the running value must be rolled back when a thread carries us back up the tree.

def sum_numbers_morris(root):
    total, acc, cur = 0, 0, root
    while cur:
        if cur.left is None:
            acc = acc * 10 + cur.val
            if cur.right is None:          # no left and no right: a real leaf
                total += acc
            cur = cur.right                 # may be a thread back up
        else:
            pred, steps = cur.left, 1
            while pred.right and pred.right is not cur:
                pred = pred.right
                steps += 1
            if pred.right is None:          # first visit: thread, then go left
                acc = acc * 10 + cur.val
                pred.right = cur
                cur = cur.left
            else:                           # second visit: returned via thread
                pred.right = None
                if pred.left is None:       # pred is a leaf in the real tree
                    total += acc
                acc //= 10 ** steps         # remove digits of the left path
                cur = cur.right
    return total

Two details carry the correctness. First, leaf detection. When we follow a thread, the node we left had a right pointer that was artificially non-null, so the cur.right is None test cannot see it as a leaf. Instead, the leaf is counted on the second visit to the ancestor: the predecessor, the rightmost node of the left subtree, had a null right pointer before we threaded it, so it was a real leaf exactly when its left pointer is also null. At that moment acc still holds the predecessor's full number.

Second, the rollback. The path from cur down to its predecessor is one step to the left child and then only right steps, so it has exactly steps nodes. Each added one digit to acc, so integer division by 10 to the power steps restores cur's prefix value. Counting steps during the same predecessor walk keeps the work O(n) overall, since each edge is walked a constant number of times.

Morris traversal mutates the tree while it runs. It is unsafe if another thread reads the tree at the same time, and an exception mid-loop leaves dangling threads. Use it only when memory is genuinely constrained and the tree is private to the call.

Testing against an oracle

Four implementations of one function are an invitation to test them against each other. A slow but obviously correct oracle builds each path as a string and parses it, so it shares none of the arithmetic with the fast versions.

import random

def oracle(root):
    out = []
    def go(n, s):
        if n is None:
            return
        s += str(n.val)
        if not n.left and not n.right:
            out.append(int(s))
        go(n.left, s); go(n.right, s)
    go(root, "")
    return sum(out)

def rand_tree(n):
    if n == 0:
        return None
    k = random.randint(0, n - 1)
    return TreeNode(random.randint(0, 9), rand_tree(k), rand_tree(n - 1 - k))

for _ in range(3000):
    t = rand_tree(random.randint(0, 25))
    want = oracle(t)
    for f in (sum_numbers, sum_numbers_stack, sum_numbers_bfs, sum_numbers_morris):
        assert f(t) == want, f.__name__

Random shapes matter more than random values: they produce single-child nodes, chains and empty trees, which is where the bugs live. Add one more assertion for Morris, that a structural snapshot of the tree is identical before and after the call, to prove every thread was removed. All four implementations in this article pass these checks.

Variants

• Binary digits. LeetCode 1022, Sum of Root To Leaf Binary Numbers, uses 0 and 1 in each node. Replace multiplication by ten with a shift: acc = (acc << 1) | node.val. Everything else is unchanged; the general form is acc * base + digit.
• Multi-digit node values. If a node may hold 42, concatenation means shifting by the number of digits in the value: acc = acc * 10 ** len(str(v)) + v. Decide in advance how a value of 0 behaves; len(str(0)) is 1, which treats it as one digit.
• Large answers. Python integers grow without limit. In Java, C++ or Go a 64-bit signed integer holds every 18-digit number, but a path of 19 or more digits can overflow, and the sum can overflow earlier when there are many leaves. LeetCode's version constrains depth to 10 and guarantees a 32-bit result; production data will not.
• Modular answers. When the result must be reported modulo a prime such as 1,000,000,007, reduce both the prefix and the total after every step. Modular arithmetic distributes over the multiply and add, so the result is exact.
• Listing the numbers. If the caller wants the individual numbers, collect each leaf's acc instead of adding it; output size, not traversal, then dominates memory.

Failure modes

These are the mistakes that appear in real submissions and code reviews, roughly in order of frequency.

1. Returning acc at a null child. Writing if node is None: return acc instead of returning 0 looks harmless, because true leaves still return early. But a node with only one child now emits its own prefix as a bogus number through the missing side. For the tree with root 1 and a single left child 2 the correct answer is 12; this bug returns 12 + 1 = 13.
2. Treating any node with one null child as a leaf. The leaf test needs both children null.
3. Shared mutable path state. Building the number in a list or string shared across calls and forgetting to pop after the recursive call produces numbers that leak digits from sibling branches.
4. Pushing children before updating acc. In the stack version, the child must receive the parent's updated prefix. Pushing before computing it drops one digit level.
5. Wrong rollback in Morris. Dividing by ten once instead of ten to the power steps, or counting steps from the wrong node, corrupts every number to the right of a deep left subtree.
6. Fixed-width overflow. Silent wraparound in languages without overflow checks gives plausible but wrong results; add a depth check or use big integers when input is not bounded.

Trade-offs

For interviews, write the recursive version, state its complexity, and mention the stack version for deep inputs. In production, prefer the explicit stack: it is robust to depth and still easy to review. Reach for Morris only with a measured memory constraint, and keep its oracle test in the suite.

What to do next

1. Implement the recursive solution from memory and check it on [1,2,3] (25) and [4,9,0,5,1] (1026).
2. Write the null-child bug deliberately, then find the smallest tree that exposes it.
3. Convert to an explicit stack and run it on a 100,000-node chain.
4. Implement Morris and add the snapshot assertion to prove the tree is restored.
5. Solve the binary variant by changing one line.
6. Move on to the path sum problems and symmetric tree exercises to practise the same top-down and bottom-up patterns.