Leetcode 129. Sum Root to Leaf Numbers

Let's understand what we're being asked to do. We have a binary tree where each node contains a single digit from 0 to 9. We need to find all paths from the root to each leaf, treat the digits along each path as forming a number, and sum all these numbers.

For example, if we have a tree with root 1, left child 2, and right child 3, we have two root-to-leaf paths: 1→2 (forming the number 12) and 1→3 (forming the number 13). The sum would be 12 + 13 = 25.

Let's trace through a more complex example: root 4, left child 9 (with children 5 and 1), right child 0. The paths are: 4→9→5 (number 495), 4→9→1 (number 491), and 4→0 (number 40). The sum is 495 + 491 + 40 = 1026.

Important constraints: Tree size can be up to 1000 nodes, depth up to 10, and each node contains a digit 0-9.

Edge cases to consider: What if the tree has only one node (the root is also a leaf)? What if a path contains leading zeros (like 0→5 forming 05, which is just 5)? What if the tree is skewed (all nodes in a single path)?

As we traverse from root to leaf, we're building a number digit by digit. If we're at a node with value 5 and the number formed so far is 12, then the new number becomes 12 * 10 + 5 = 125.

This means we can accumulate the number as we go down rather than storing the entire path and converting it at the end.

By building the number incrementally during traversal, we avoid storing paths and doing string-to-number conversions. When we reach a leaf node, we already have the complete number formed by that path.

This transforms the problem from 'collect all paths then process' to 'process as we traverse', which is more efficient in both time and space.

Think about how you read a number left-to-right: when you see '1', you have 1. When you see the next digit '2', you shift the previous number left (multiply by 10) and add the new digit: 1 * 10 + 2 = 12. When you see '3', you do it again: 12 * 10 + 3 = 123.

Tree traversal works the same way! As we go down from parent to child, we're reading digits left-to-right. When we reach a leaf (no more children), we've read the complete number and can add it to our sum.

Use depth-first search (DFS) to traverse the tree from root to leaves. As we traverse down each path, maintain a running number by multiplying the current number by 10 and adding the current node's digit. When we reach a leaf node (no children), add the accumulated number to our total sum. Recursively explore both left and right subtrees, backtracking naturally as the recursion unwinds. This approach visits each node exactly once and processes each path efficiently.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def sum_root_to_leaf(root):
    """
    Compute sum of all root-to-leaf path numbers using DFS.
    Time: O(n), Space: O(h) where h is tree height.
    """
    def dfs(node, current_number):
        # Base case: empty node
        if not node:
            return 0
        
        # Build current path number
        current_number = current_number * 10 + node.val
        
        # Leaf node: return accumulated number
        if not node.left and not node.right:
            return current_number
        
        # Recursively explore left and right subtrees
        left_sum = dfs(node.left, current_number)
        right_sum = dfs(node.right, current_number)
        
        # Return total sum from both subtrees
        return left_sum + right_sum
    
    # Start DFS from root with initial number 0
    return dfs(root, 0)

• DFS path accumulation pattern: When you need to track values along a path from root to leaf in a tree, use DFS with accumulated state passed as a parameter - multiply the current path value by 10 and add the new digit at each level, naturally building the number as you traverse downward.
• Leaf node identification: A critical implementation detail is correctly identifying leaf nodes with `if not node.left and not node.right` - only accumulate the final number when reaching a leaf, not at every node, to avoid counting partial paths.
• Recursive state passing vs global state: Pass the accumulated path value as a function parameter (e.g., `dfs(node, current_sum * 10 + node.val)`) rather than using global variables - this automatically handles backtracking and keeps each path's calculation independent without manual cleanup.
• Base case ordering matters: Always check `if not node: return 0` before checking for leaf nodes - this prevents null pointer errors when recursing on `node.left` or `node.right` that don't exist, and ensures clean termination of recursive branches.
• O(n) time with implicit backtracking: This solution achieves O(n) time and O(h) space because each node is visited once, and the call stack depth equals tree height - the accumulated value is passed by value (in most languages), so backtracking happens automatically without extra operations.
• Path-to-value aggregation pattern: This technique extends to any problem requiring aggregation of values along tree paths - such as finding max/min path sums, counting paths with specific properties, or building strings from root to leaf - the key is recognizing when you need to accumulate state during traversal and sum results at leaf nodes.