LeetCode 129 - Sum Root to Leaf Numbers

The problem gives us the root of a binary tree where every node contains a single digit from 0 to 9. Every path starting from the root and ending at a leaf node forms a number by concatenating the digits along that path.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 129

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree where every node contains a single digit from 0 to 9. Every path starting from the root and ending at a leaf node forms a number by concatenating the digits along that path.

For example, consider the path:

1 -> 2 -> 3

This path represents the number 123.

The goal is to compute the sum of all such root-to-leaf numbers in the tree.

A leaf node is defined as a node with no left child and no right child. Only complete root-to-leaf paths count toward the final sum.

The input is a binary tree, not an array of numbers. Each node contributes one digit to the current number being formed. As we move deeper into the tree, we effectively append digits to the current number. Appending a digit to a decimal number means multiplying the current value by 10 and adding the new digit.

For example:

Current number = 49
Next digit = 5

New number = 49 * 10 + 5 = 495

The constraints are important:

  • The tree contains at most 1000 nodes.
  • The depth of the tree does not exceed 10.
  • Every node value is a digit between 0 and 9.

These constraints tell us that recursion is completely safe because the maximum recursion depth is very small. They also imply that a traversal-based solution is efficient enough because visiting every node once only costs O(n) time.

Several edge cases are worth considering immediately.

A tree with only one node should return that node's value directly because the single node is both the root and a leaf. Trees containing zeros can be tricky because leading or intermediate zeros still participate in number formation. For example, the path 1 -> 0 -> 5 represents 105, not 15. Skewed trees, where every node only has one child, should still work correctly because there is still exactly one root-to-leaf path. Finally, we must ensure that we only add numbers when we reach leaf nodes, not intermediate nodes.

Approaches

Brute Force Approach

A straightforward brute-force strategy is to explicitly build every root-to-leaf path as a string or list of digits. Once a leaf node is reached, we convert the collected digits into an integer and add it to the answer.

For example, during traversal we might store:

[4, 9, 5]

At the leaf, we would convert it into "495" and then into the integer 495.

This approach works because it explores every possible root-to-leaf path and correctly reconstructs the number represented by each path. However, it performs unnecessary work because every leaf requires rebuilding or converting an entire path representation into a number.

Although the constraints are small enough that this solution would still pass, it is inefficient conceptually because repeated string concatenation or list copying introduces extra overhead.

Key Insight

The important observation is that we do not need to store the entire path explicitly.

As we traverse downward, we can maintain the numeric value represented by the current path. When moving to a child node, we append the child digit mathematically:

new_value = current_value * 10 + child.val

This means we can compute the path number incrementally during traversal.

Once we reach a leaf node, the current accumulated value is already the complete root-to-leaf number, so we simply add it to the total.

This naturally leads to a Depth-First Search solution because DFS explores one path completely before backtracking to another.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × h) O(h) Stores path digits and reconstructs numbers repeatedly
Optimal O(n) O(h) Builds numbers incrementally during DFS traversal

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

  1. Start a Depth-First Search from the root node.

DFS is ideal because the problem is fundamentally about exploring complete root-to-leaf paths. Each recursive call represents moving one level deeper into the current path. 2. Maintain a running number during traversal.

At every node, update the current number using:

$current = current \times 10 + node.val$

This appends the node's digit to the existing number exactly the same way decimal numbers are formed. 3. Check whether the current node is a leaf.

A node is a leaf if both left and right are None.

If we reach a leaf, the current accumulated number represents one complete root-to-leaf number, so we return it. 4. Recursively process the left and right subtrees.

Continue DFS into both children while passing the updated current number. 5. Combine the subtree results.

The total sum contributed by the current node equals:

left_sum + right_sum

because every valid root-to-leaf path must belong to either the left subtree or the right subtree. 6. Return the final accumulated sum.

The recursive calls naturally aggregate the total across all root-to-leaf paths.

Why it works

The algorithm maintains the invariant that the current variable always equals the numeric value represented by the path from the root to the current node.

Each recursive call extends the path by one digit using decimal-place arithmetic. Since DFS visits every root-to-leaf path exactly once and every leaf contributes exactly one valid number, the final sum is correct.

Python Solution

# 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], current_number: int) -> int:
            if not node:
                return 0
            
            current_number = current_number * 10 + node.val
            
            # Leaf node
            if not node.left and not node.right:
                return current_number
            
            left_sum = dfs(node.left, current_number)
            right_sum = dfs(node.right, current_number)
            
            return left_sum + right_sum
        
        return dfs(root, 0)

The implementation uses a nested helper function named dfs. This function receives two pieces of information: the current node and the number formed so far along the current path.

The base case handles None nodes by returning 0. This simplifies the recursive logic because missing children contribute nothing to the final sum.

At each node, the current path value is updated by multiplying the previous value by 10 and adding the current digit. This mirrors decimal number construction.

When a leaf node is reached, the function returns the completed number immediately. Otherwise, the function recursively computes the sums from the left and right subtrees and combines them.

The main function starts the traversal with an initial path value of 0.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    
    var dfs func(node *TreeNode, currentNumber int) int
    
    dfs = func(node *TreeNode, currentNumber int) int {
        if node == nil {
            return 0
        }
        
        currentNumber = currentNumber*10 + node.Val
        
        // Leaf node
        if node.Left == nil && node.Right == nil {
            return currentNumber
        }
        
        leftSum := dfs(node.Left, currentNumber)
        rightSum := dfs(node.Right, currentNumber)
        
        return leftSum + rightSum
    }
    
    return dfs(root, 0)
}

The Go solution follows exactly the same recursive structure as the Python version. The main difference is that Go requires explicit pointer checks using nil.

A recursive function variable is declared first and assigned afterward because anonymous recursive functions in Go require this two-step declaration pattern.

Integer overflow is not a concern because the problem guarantees the final answer fits inside a 32-bit integer.

Worked Examples

Example 1

Input:

root = [1,2,3]

Tree:

    1
   / \
  2   3

Traversal process:

Current Node Previous Number Updated Number Leaf? Contribution
1 0 1 No Continue
2 1 12 Yes 12
3 1 13 Yes 13

Final computation:

12 + 13 = 25

Output:

25

Example 2

Input:

root = [4,9,0,5,1]

Tree:

      4
     / \
    9   0
   / \
  5   1

Traversal process:

Current Node Previous Number Updated Number Leaf? Contribution
4 0 4 No Continue
9 4 49 No Continue
5 49 495 Yes 495
1 49 491 Yes 491
0 4 40 Yes 40

Final computation:

495 + 491 + 40 = 1026

Output:

1026

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack stores at most one path from root to leaf

The DFS traversal processes each node one time and performs only constant-time work per node. Therefore, the total time complexity is linear in the number of nodes.

The space complexity comes entirely from recursion depth. In the worst case of a completely skewed tree, the recursion stack can contain h calls simultaneously, where h is the tree height. Since the maximum depth is at most 10, recursion is very safe for this problem.

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.sumNumbers(root1) == 25  # Basic two-leaf tree

# Example 2
root2 = TreeNode(
    4,
    TreeNode(9, TreeNode(5), TreeNode(1)),
    TreeNode(0)
)
assert solution.sumNumbers(root2) == 1026  # Multiple root-to-leaf paths

# Single node tree
root3 = TreeNode(7)
assert solution.sumNumbers(root3) == 7  # Root is also leaf

# Tree containing zeros
root4 = TreeNode(1, TreeNode(0), TreeNode(5))
assert solution.sumNumbers(root4) == 25  # Paths are 10 and 15

# Left-skewed tree
root5 = TreeNode(1, TreeNode(2, TreeNode(3)))
assert solution.sumNumbers(root5) == 123  # Only one path

# Right-skewed tree
root6 = TreeNode(9, None, TreeNode(8, None, TreeNode(7)))
assert solution.sumNumbers(root6) == 987  # Deep single path

# Mixed tree
root7 = TreeNode(
    2,
    TreeNode(3, TreeNode(4), TreeNode(5)),
    TreeNode(1)
)
assert solution.sumNumbers(root7) == 470  # 234 + 235 + 21

# All zeros
root8 = TreeNode(0, TreeNode(0), TreeNode(0))
assert solution.sumNumbers(root8) == 0  # Multiple zero-valued paths

# Deep tree
root9 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.sumNumbers(root9) == 1234  # Deep recursion path
Test Why
[1,2,3] Verifies the basic example
[4,9,0,5,1] Tests multiple subtree paths
Single node tree Ensures root-only trees work
Tree containing zeros Validates handling of digit 0
Left-skewed tree Tests recursion on one-sided depth
Right-skewed tree Verifies asymmetric traversal
Mixed tree Confirms summation across multiple leaves
All zeros Ensures numeric construction handles zeros correctly
Deep tree Tests recursive depth handling

Edge Cases

A single-node tree is one of the most important edge cases. In this situation, the root is also a leaf. A buggy implementation might continue recursion unnecessarily or fail to recognize that the single digit itself forms a valid number. The current implementation handles this naturally because the leaf-node condition is checked immediately after updating the current number.

Trees containing zeros can also cause subtle bugs. Some implementations accidentally treat zeros as insignificant digits or incorrectly skip them. However, zeros are valid digits within the number. For example, the path 1 -> 0 -> 5 must become 105. The formula:

$current = current \times 10 + digit$

correctly preserves zeros in the proper decimal position.

Skewed trees are another important case. A tree may effectively behave like a linked list if every node has only one child. Recursive solutions with poor base-case handling may incorrectly stop traversal or double-count nodes. This implementation works correctly because every recursive call independently processes whichever child exists, and None children simply return 0.

Another subtle edge case occurs when internal nodes should not contribute directly to the sum. Only complete root-to-leaf paths count. A buggy implementation might accidentally add intermediate path values before reaching leaves. The current solution avoids this by returning the accumulated number only when both child pointers are None.