Domain 2MediumCORE

Sum Root to Leaf Numbers

We are given the root of a binary tree where every node contains a single digit (0-9). The core task is to treat each path from the root down to any leaf as a decimal number and sum them all up.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Depth-first Search

129. Sum Root to Leaf Numbers

Model: qwen3.5:9b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 51.3%


Problem Breakdown

We are given the root of a binary tree where every node contains a single digit (0-9). The core task is to treat each path from the root down to any leaf as a decimal number and sum them all up.

For example, if we have 1 -> 2, that represents the integer 12. If there’s another branch 1 -> 3, it represents 13. We need to return 12+13=2512 + 13 = 25.

Key Inputs: A binary tree root node (TreeNode). Output: An integer representing the total sum of all valid paths. Implicit Constraints & Edge Cases:

  • Leaf Definition: Only nodes with no children count as leaves for a path termination. If a node has only one child, it is not a leaf; we must continue down that branch.
  • Empty Tree: The constraints state the number of nodes is at least 1, so root will never be null initially. However, our recursion logic should handle children being null gracefully.
  • Overflow: With depth up to 10 and digits 9-9, a path could represent ≈1010\approx 10^{10}. In languages like Java or C++, this exceeds the standard signed 32-bit integer limit (≈2×109\approx 2 \times 10^9), requiring long. Python handles large integers automatically, so we don’t need to worry about overflow here.

Intuition

A brute-force approach would be to traverse every path from root to leaf, store the number formed by each path in a list or string buffer, and then convert them all to integers at the end for summation. While this works logically, it is inefficient because we are storing intermediate states unnecessarily. We can optimize space significantly if we carry the “current number” down with us as we traverse.

The key insight here is that when moving from a parent node to a child node in a decimal system:

  1. The current accumulated value needs its digits shifted left (multiplied by 10).
  2. We add the new digit (node.val).

So, if current_sum at the root is XX, and we move to a child with value YY, the new sum becomes (X×10)+Y(X \times 10) + Y.

This suggests a Depth-First Search (DFS). As we recurse down:

  • If we hit a leaf node, the current accumulated current_sum is our contribution. We return it immediately.
  • If we are at an internal node, we update the sum and recursively call for left and right children. The total result is the sum of what comes back from both subtrees (if they exist).

Approach

We will use a recursive DFS helper function that takes two arguments:

  1. node: The current tree node being visited.
  2. current_sum: An integer representing the number formed by the path so far.

Algorithm Steps:

  1. Base Case (Leaf): If node is null, return 0. However, strictly speaking for a leaf check: if both left and right children are missing, we treat this node as contributing its current accumulated value to the total sum.
  2. Recursive Step: Update current_sum: new_sum=(current_sum×10)+node.val\text{new\_sum} = (\text{current\_sum} \times 10) + \text{node.val}
  3. Accumulate Results: If a left child exists, add the result of recursing on it to our total. Do the same for the right child if it exists.
  4. Return Total: Return left_result + right_result.

Note: To keep code clean and avoid checking “is leaf” explicitly inside every call (which can be messy), we handle null nodes by returning 0, but ensure that when a node is truly a leaf (both children are None), the recursion returns its value. Actually, simpler logic: If node has no left child AND no right child, return current_sum. Otherwise recurse on existing children and sum their results.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes in the tree. We visit every node exactly once to calculate its contribution or pass it down.
  • Space Complexity: O(H)O(H), where HH is the height of the tree. This accounts for the recursion stack space used during DFS traversal. In a balanced tree this is O(log⁡N)O(\log N); in a skewed (linked-list-like) tree, it degrades to O(N)O(N). Given constraints state depth ≤10\le 10, stack overflow is not a concern here.

Solution

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

def sumNumbers(root: 'TreeNode') -> int:
    """
    Calculates the sum of all root-to-leaf numbers.
    
    Args:
        root (TreeNode): The root node of the binary tree containing digits 0-9.
        
    Returns:
        int: Sum of all paths from root to leaf interpreted as decimal integers.
    """
    
    def dfs(node, current_sum):
        # If we reach a null child, it contributes nothing to this path sum 
        if not node:
            return 0
        
        # Update the running number for this level
        new_current = (current_sum * 10) + node.val
        
        # Check if leaf node (no children left or right)
        if not node.left and not node.right:
            return new_current
        
        # Recurse on existing children, summing their results. 
        # If a child is None, dfs returns 0 immediately above, so this works safely.
        total = dfs(node.left, new_current) + dfs(node.right, new_current)
        
        return total

    if not root:
        return 0
        
    return dfs(root, 0)

Edge Cases Handled

  • Single Node Tree: If the tree has only one node (root is a leaf), dfs updates sum to node.val, checks for children (none found), and returns that value. Correctly sums as just that digit.
  • Null Children in Recursion: The helper function handles null nodes by returning 0 immediately, preventing index errors or attribute access on None objects during the recursive step (dfs(node.left...)).
  • Zero Values: Nodes with val = 0 are handled correctly (e.g., path 1 -> 0 -> 5 becomes 1×10+0=101 \times 10 + 0 = 10, then 10×10+5=10510 \times 10 + 5 = 105).
  • Deep Trees: While recursion depth is limited by system stack, the problem constraints explicitly limit tree height to 10. Even without that constraint, Python’s default recursion limit (usually 1000) covers N=1000N=1000.