Sum Root to Leaf Numbers

Problem

You are given the root of a binary tree in which every node holds a single digit (0–9). Each root-to-leaf path spells out a number: reading the digits from the root down to the leaf gives a decimal integer (e.g. the path 1 → 2 → 3 represents 123).

Return the sum of all the numbers spelled by every root-to-leaf path.

A leaf is a node with no children. The tree is guaranteed to have at least one node, and the total fits in a 32-bit signed integer.

Examples

Example 1

Input: root = [1,2,3]
Output: 25

Paths: 1 → 2 = 12, and 1 → 3 = 13. Sum = 12 + 13 = 25.

Example 2

Input: root = [4,9,0,5,1]
Output: 1026

Paths: 4 → 9 → 5 = 495, 4 → 9 → 1 = 491, 4 → 0 = 40. Sum = 495 + 491 + 40 = 1026.

Example 3

Input: root = [7]
Output: 7

A single node is itself a leaf; the only path spells 7.

Constraints

• The number of nodes is in the range [1, 1000].
• 0 <= Node.val <= 9
• The tree depth is at most 10, so each number has at most 10 digits and the sum fits in a 32-bit integer.

Think about it first

TL;DR

DFS carrying the number built so far, summing at leaves — O(n) time, O(h) space.

Approach 1 — Brute force: collect every path, then convert and sum

The naive idea builds each root-to-leaf path as a list of digits, converts each to an integer, and sums them.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


def sumNumbers(root: Optional[TreeNode]) -> int:
    paths: List[str] = []

    def collect(node: Optional[TreeNode], digits: str) -> None:
        if not node:
            return
        digits += str(node.val)
        if not node.left and not node.right:
            paths.append(digits)
        else:
            collect(node.left, digits)
            collect(node.right, digits)

    collect(root, "")
    return sum(int(p) for p in paths)

Complexity: O(n · h) time — each of up to O(n) leaves stores and re-parses a string of length up to h. O(n · h) space for the stored strings. It works within the tiny constraints, but building and re-parsing strings is unnecessary: the number can be carried as an integer during the walk.

Approach 2 — DFS carrying the running number (recursive)

You never need the whole path, only the integer built so far. Stepping from a partial number cur to a child with digit d shifts left one decimal place: cur * 10 + d. Add to the total only at a leaf. This is a depth-first search (DFS): fully explore one branch before backtracking.

Example 2 (root = [4,9,0,5,1]) as a tree, with the number carried into each node:

flowchart TD
    A["4 · cur=4"] --> B["9 · cur=49"]
    A --> C["0 · cur=40 (leaf → 40)"]
    B --> D["5 · cur=495 (leaf → 495)"]
    B --> E["1 · cur=491 (leaf → 491)"]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def sumNumbers(root: Optional[TreeNode]) -> int:
    def dfs(node: Optional[TreeNode], cur: int) -> int:
        if not node:
            return 0
        cur = cur * 10 + node.val
        if not node.left and not node.right:
            return cur
        return dfs(node.left, cur) + dfs(node.right, cur)

    return dfs(root, 0)

Walkthrough on Example 2 (root = [4,9,0,5,1]: 4 with left 9(children 5,1) and right 0):

1. dfs(4, 0) → cur = 4. Not a leaf. Return dfs(9, 4) + dfs(0, 4).
2. dfs(9, 4) → cur = 49. Not a leaf. Return dfs(5, 49) + dfs(1, 49).
3. dfs(5, 49) → cur = 495, leaf → returns 495.
4. dfs(1, 49) → cur = 491, leaf → returns 491. So dfs(9,4) = 986.
5. dfs(0, 4) → cur = 40, leaf → returns 40.
6. Total 986 + 40 = 1026.

Complexity: O(n) time — each node visited once. O(h) space for the recursion stack (h = height; O(n) worst case, O(log n) balanced).

Approach 3 — Iterative DFS with an explicit stack

The recursion carries just one integer per frame, so replace the call stack with an explicit stack of (node, cur) pairs. This avoids Python’s recursion limit on very deep trees and makes the accumulation explicit.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def sumNumbers(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    total = 0
    stack = [(root, 0)]
    while stack:
        node, cur = stack.pop()
        cur = cur * 10 + node.val
        if not node.left and not node.right:
            total += cur
        if node.right:
            stack.append((node.right, cur))
        if node.left:
            stack.append((node.left, cur))
    return total

Walkthrough on Example 1 (root = [1,2,3]): push (1,0). Pop (1,0) → cur = 1, not leaf, push (3,1) and (2,1). Pop (2,1) → cur = 12, leaf → total = 12. Pop (3,1) → cur = 13, leaf → total = 25. Result 25.

Complexity: O(n) time, O(h) space for the stack (O(n) worst case).

Common pitfalls

• Adding non-leaf nodes: only add cur to the total at a leaf (not node.left and not node.right). Adding at internal nodes double-counts prefixes.
• A one-child node is not a leaf: a node with only a left child must recurse into that child, not be treated as a terminal — the dfs(None, …) call simply returns 0.
• Resetting vs. carrying cur: cur must be passed down by value (each recursive call gets its own cur * 10 + node.val); a shared mutable accumulator would leak digits across sibling branches.
• Building strings needlessly: integer arithmetic (cur * 10 + d) is cleaner and avoids parsing; Python big-ints mean there is no overflow, but the constraints keep values small anyway.

Pattern takeaway

When a tree problem accumulates information along a root-to-leaf path, thread that partial state down as a function argument and finalize it at the leaf. The “shift and add” update cur * 10 + digit is the tree analogue of building a number digit by digit — and any such single-value downward state converts mechanically into an iterative stack of (node, state) pairs.