LeetCode 129: Sum Root to Leaf Numbers

Problem Restatement

We are given the root of a binary tree.

Each node contains a digit from 0 to 9.

Every root-to-leaf path represents one number. For example, the path 1 -> 2 -> 3 represents the number 123.

We need to return the sum of all numbers formed by all root-to-leaf paths. A leaf is a node with no children. The answer is guaranteed to fit in a 32-bit integer.

Examples

Example 1:

    1
   / \
  2   3

There are two root-to-leaf paths:

1 -> 2  represents 12
1 -> 3  represents 13

So the answer is:

12 + 13 = 25

Output:

25

Example 2:

      4
     / \
    9   0
   / \
  5   1

The root-to-leaf paths are:

4 -> 9 -> 5  represents 495
4 -> 9 -> 1  represents 491
4 -> 0       represents 40

So the answer is:

495 + 491 + 40 = 1026

Output:

1026

Input and Output

Function shape:

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        ...

Core Idea

As we walk down a path, we build the current number digit by digit.

Suppose the current path is:

1 -> 2 -> 3

We build the number like this:

start = 0
after 1: 0 * 10 + 1 = 1
after 2: 1 * 10 + 2 = 12
after 3: 12 * 10 + 3 = 123

So when we visit a node, the update rule is:

current = current * 10 + node.val

This works because multiplying by 10 shifts the previous digits one decimal place to the left, then node.val becomes the new last digit.

Why DFS Fits

A root-to-leaf number depends on the full path from the root to one leaf.

Depth-first search naturally follows one full path before returning to explore another path.

At each node, DFS carries the number formed so far.

When DFS reaches a leaf, the current number is complete, so we return it.

Then parent calls add the sums from their left and right subtrees.

Algorithm

Use a recursive helper:

dfs(node, current)

where:

For each call:

1. If node is None, return 0.
2. Update current = current * 10 + node.val.
3. If node is a leaf, return current.
4. Recursively compute the left subtree sum.
5. Recursively compute the right subtree sum.
6. Return left_sum + right_sum.

Correctness

At every node, current equals the number formed by the path from the root to that node.

This is true at the root because we start with 0, then append the root digit.

If it is true for a parent, then for a child the update:

current * 10 + child.val

correctly appends the child digit to the parent path number.

When the DFS reaches a leaf, the path cannot continue. Therefore, the current value is exactly one complete root-to-leaf number.

The recursion returns that number for each leaf and adds the results from all subtrees. Since every root-to-leaf path ends at exactly one leaf, every valid number is counted once.

Therefore, the algorithm returns the total sum of all root-to-leaf numbers.

Complexity

Let n be the number of nodes in the tree, and let h be the height of the tree.

In the worst case, a skewed tree has height n, so the space can be O(n).

In a balanced tree, the height is O(log n).

Implementation

from typing import Optional

# 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

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if node is None:
                return 0

            current = current * 10 + node.val

            if node.left is None and node.right is None:
                return current

            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)

Code Explanation

The helper receives the current node and the number formed before this node:

def dfs(node: Optional[TreeNode], current: int) -> int:

If the node is missing, it contributes nothing:

if node is None:
    return 0

Then we append the current digit:

current = current * 10 + node.val

If this node is a leaf, the number is complete:

if node.left is None and node.right is None:
    return current

Otherwise, the answer from this subtree is the sum of the answers from its children:

return dfs(node.left, current) + dfs(node.right, current)

The main function starts with no digits accumulated:

return dfs(root, 0)

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.sumNumbers(root) == 25

    root = TreeNode(
        4,
        TreeNode(9, TreeNode(5), TreeNode(1)),
        TreeNode(0),
    )
    assert s.sumNumbers(root) == 1026

    root = TreeNode(7)
    assert s.sumNumbers(root) == 7

    root = TreeNode(0, TreeNode(1), TreeNode(2))
    assert s.sumNumbers(root) == 3

    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert s.sumNumbers(root) == 123

    print("all tests passed")

run_tests()

Test meaning: