← ~/lc-grind/posts

#129 - Sum Root to Leaf Numbers

November 12, 2025

Sum Root to Leaf Numbers

Problem Description

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

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

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:


Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:


Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement: We are given a binary tree where each node contains a single digit (0-9). The objective is to compute the sum of all numerical values formed by concatenating digits along every possible root-to-leaf path. A root-to-leaf path is defined as any sequence starting from the root node and terminating at a leaf node (a node with no children). The concatenated digits form base-10 numbers, and we must return the arithmetic sum of all such numbers. The solution must operate within computational bounds suitable for trees with up to 1000 nodes and depth ≤10.

Beginner-Friendly Explanation: Imagine you’re walking through a family tree where each person holds a single digit (0-9). Starting from the oldest ancestor (root), you write down each digit you encounter as you follow different family lines until you reach someone with no children (leaf). Each complete path gives you a multi-digit number. Your task is to add up all these numbers from every possible complete path in the family tree.

Mathematical Formulation: Let T be a binary tree with n nodes, where each node v has value d(v) ∈ {0,1,…,9}. Let P be the set of all root-to-leaf paths. For a path p = (v₁, v₂, …, vₖ) ∈ P, the numerical value is:

N(p)=∑i=1kd(vi)⋅10k−iN(p) = \sum_{i=1}^{k} d(v_i) \cdot 10^{k-i}

The target sum is:

S=∑p∈PN(p)S = \sum_{p \in P} N(p)

Constraint Analysis:

  • Number of nodes in [1, 1000]: Eliminates exponential solutions. O(n²) is acceptable but O(n) is ideal.
  • Node values 0-9: No negative numbers or multi-digit values. Leading zeros are possible but don’t affect arithmetic.
  • Depth ≤ 10: Critical optimization insight. Maximum path length is 10 digits → maximum number is 999,999,999 (fits in 32-bit integer). No overflow concerns.
  • Hidden edge cases: Single-node trees (path = node value), trees with all left/right children, paths with leading zeros (e.g., 0->5 = 5), and unbalanced trees.

2. Intuition Scaffolding

Real-World Metaphor: Think of the tree as a corporate hierarchy where each employee has an ID digit. The CEO (root) wants to evaluate all promotion paths to junior employees (leaves). Each path’s “score” is the concatenated ID numbers. The total sum represents the organization’s cumulative promotion path value.

Gaming Analogy: Like a skill tree in RPG games where each node gives a skill point (digit). Following different upgrade paths creates unique skill combinations (numbers). The total sum is your character’s overall power rating across all possible builds.

Math Analogy: This is equivalent to computing the weighted sum of leaf nodes where weights are determined by the path depth. Each node contributes its value multiplied by 10^(depth_from_leaf), creating a positional number system distributed across the tree.

Common Pitfalls:

  1. Global accumulator confusion: Modifying a single variable across recursive calls without proper state management
  2. Path contamination: Not backtracking properly when using mutable data structures
  3. Leaf misidentification: Counting non-leaf nodes as path endpoints
  4. Base case errors: Forgetting the single-node tree case
  5. Integer overflow: Though constrained, using strings then converting could cause issues
  6. Leading zero mishandling: Treating “0->5” as “05” = 5, not 5 or 105

3. Approach Encyclopedia

Brute Force - Path Collection:

def sumNumbers(root):
    all_paths = []
    
    def dfs(node, current_path):
        if not node: return
        current_path.append(str(node.val))
        if not node.left and not node.right:  # Leaf
            all_paths.append(int(''.join(current_path)))
        dfs(node.left, current_path)
        dfs(node.right, current_path)
        current_path.pop()  # Backtrack
    
    dfs(root, [])
    return sum(all_paths)

Complexity: Time O(n + L⋅d) where L = leaf count, d = depth (string operations). Space O(n + L⋅d) for path storage.

Optimized DFS - Progressive Calculation:

def sumNumbers(root):
    def dfs(node, current_sum):
        if not node: return 0
        current_sum = current_sum * 10 + node.val
        if not node.left and not node.right:
            return current_sum
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)
    
    return dfs(root, 0)

Complexity Proof: Each node visited once → O(n). Space O(h) for recursion stack, h ≤ 10 → O(1) effectively.

Visualization (Example 1):

Initial: (1,0)
    ↓ Calculate: 0×10 + 1 = 1
    /          \
(2,1)        (3,1)
  ↓             ↓
1×10+2=12    1×10+3=13
Leaf!        Leaf!
Return: 12 + 13 = 25

BFS - Level Order Approach:

from collections import deque

def sumNumbers(root):
    if not root: return 0
    queue = deque([(root, root.val)])
    total = 0
    
    while queue:
        node, value = queue.popleft()
        if not node.left and not node.right:
            total += value
        if node.left:
            queue.append((node.left, value * 10 + node.left.val))
        if node.right:
            queue.append((node.right, value * 10 + node.right.val))
    
    return total

Complexity: Time O(n), Space O(w) where w = maximum level width.

4. Code Deep Dive

Optimal Solution (DFS):

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_sum):
            # Base case: null node contributes nothing
            if not node:
                return 0
                
            # Update running total with current node's value
            # Mathematical: current_sum = current_sum × 10 + d(v)
            current_sum = current_sum * 10 + node.val
            
            # Leaf detection - if both children absent, return computed value
            if not node.left and not node.right:
                return current_sum
                
            # Recursively sum left and right subtrees
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        
        # Start DFS with root and initial sum 0
        return dfs(root, 0)

Edge Case Handling:

  • Single node [5]: dfs(5,0) → current_sum = 0*10 + 5 = 5 → leaf → return 5 ✓
  • Example 1 [1,2,3]: As visualized above, correctly sums 12 + 13 = 25 ✓
  • Leading zero [0,1]: Path “0->1” = (0×10+0)=0 → (0×10+1)=1 ✓
  • Left-skewed tree: Properly accumulates all left paths without right contamination ✓

5. Complexity War Room

Hardware-Aware Analysis:

  • 1000 nodes × 4 bytes = ~4KB for recursion stack (negligible)
  • Fits in L1 cache (32-64KB typical)
  • Depth ≤10 means maximum 10 recursive calls → minimal stack overhead
  • Integer operations are CPU-friendly vs string manipulation

Industry Comparison Table:

Approach Time Space Readability Interview Viability
Path Collection O(n + Ld) O(n + Ld) 8/10 ❌ Inefficient
DFS Optimal O(n) O(h) 9/10 ✅ Recommended
BFS Iterative O(n) O(w) 7/10 ✅ Good alternative
Morris Traversal O(n) O(1) 4/10 ❌ Too complex

6. Pro Mode Extras

Variants Section:

  1. Binary Sum Root to Leaf (LC 1022): Same problem but binary numbers instead of decimal
  2. Maximum Path Sum (LC 124): Find maximum path sum (not just root-to-leaf)
  3. Path Sum II (LC 113): Return all paths that sum to target
  4. K-ary Tree Version: Extend to trees with up to k children per node
  5. Allow Negative Numbers: Would require different accumulation strategy

Interview Cheat Sheet:

  • First Mention: “This is a tree traversal problem with O(n) time, O(h) space”
  • Key Insight: “We can compute numbers progressively rather than storing paths”
  • Testing Strategy: “Check single node, unbalanced trees, and leading zeros”
  • Optimization Note: “The depth constraint makes recursion stack negligible”
  • Common Follow-up: “How would you modify this if we needed the actual paths?”