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


class Solution:
    def sumNumbers(self, 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)

The insight: 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. Finish (add to the total) only at a leaf. This is a depth-first search (DFS): fully explore one branch before backtracking.

# 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


class Solution:
    def sumNumbers(self, 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 insight: the recursion carries just one integer per frame, so replace the call stack with a stack of (node, cur) pairs. Useful for very deep trees that might exceed Python’s recursion limit, and it 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


class Solution:
    def sumNumbers(self, 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.