Problem Description

You have a binary tree where each node contains a single digit (0-9). Your task is to find the sum of all numbers formed by paths from the root to leaf nodes.

A path from root to leaf forms a number by concatenating the digits along the path. For instance, if you traverse from root to leaf through nodes with values 1 → 2 → 3, this path represents the number 123.

Key Points:

• Each node contains only a single digit (0-9)
• A leaf node is defined as a node with no children
• You need to find all root-to-leaf paths
• Each path forms a number by reading the digits from root to leaf
• Return the sum of all these numbers

Example Walkthrough:

If you have a tree where:

• Root is 1
• Root's left child is 2
• Root's right child is 3

This gives you two paths:

• Path 1: 1 → 2 forms the number 12
• Path 2: 1 → 3 forms the number 13
• Total sum: 12 + 13 = 25

The solution uses a depth-first search (DFS) approach with a helper function dfs(root, s) where s tracks the current number being formed. At each node, the current number is updated by multiplying the previous value by 10 and adding the current node's value: s = s * 10 + root.val. When a leaf node is reached, the formed number is returned. For non-leaf nodes, the function recursively calculates the sum for both left and right subtrees.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure. We have a root node, and each node can have left and right children, with no cycles present.

DFS

• Based on the flowchart, when we confirm it's a tree structure, the natural choice is DFS (Depth-First Search).

Why DFS is appropriate here:

• We need to traverse from root to each leaf node to form complete numbers
• We need to maintain the current path's accumulated value as we traverse
• At each leaf node, we need to return the formed number
• DFS naturally handles this recursive path exploration where we build up the number as we go deeper into the tree

Conclusion: The flowchart correctly leads us to use DFS for this problem. The DFS approach allows us to:

1. Traverse each root-to-leaf path completely
2. Accumulate the number formed along each path (by multiplying by 10 and adding the current digit)
3. Sum all the numbers when we reach leaf nodes
4. Backtrack naturally to explore other paths

This aligns perfectly with the solution's recursive dfs(root, s) function that tracks the current number s as it traverses down each path.

Intuition

When we look at this problem, we need to understand how numbers are formed along paths. Each path from root to leaf creates a multi-digit number by concatenating the digits. The key insight is that as we move down the tree, we're essentially "shifting" our current number left by one decimal place and adding the new digit.

Think about how we build a number like 123:

• Start with 1
• Move to next node with value 2: 1 * 10 + 2 = 12
• Move to next node with value 3: 12 * 10 + 3 = 123

This pattern current_number * 10 + new_digit is the core of our solution.

Since we need to explore every root-to-leaf path and we're dealing with a tree structure, DFS becomes the natural choice. Why? Because DFS allows us to:

1. Go deep into one path completely before exploring another
2. Maintain the "state" of our current number as we traverse
3. Naturally backtrack when we finish a path

The recursive nature of DFS matches perfectly with the recursive structure of the tree. At each node, we have a simple decision:

• If it's a leaf node (no children), we've completed forming a number - return it
• If it has children, continue building the number and explore both left and right subtrees

The beauty of this approach is that the recursion stack naturally handles the "memory" of what number we've built so far on each path. When we backtrack from a leaf, the previous state is automatically restored, allowing us to explore other branches with the correct partial number.

This is why we pass the accumulated number s as a parameter in our recursive function - it represents the number formed from root to the current node, and we update it at each step using the formula s * 10 + root.val.

Solution Approach

The solution implements a DFS approach using a helper function dfs(root, s) where s represents the accumulated number from the root to the current node.

Implementation Details:

1. Base Case - Null Node:

   • If root is None, return 0
   • This handles the case when we traverse beyond leaf nodes

2. Number Building:

   • Update the current number: s = s * 10 + root.val
   • This shifts the existing number left by one decimal place and adds the current digit
   • For example, if s = 12 and root.val = 3, then s becomes 123

3. Leaf Node Check:

   • If both root.left is None and root.right is None, we've reached a leaf
   • Return the complete number s formed along this path

4. Recursive Exploration:

   • For non-leaf nodes, recursively explore both subtrees
   • Return dfs(root.left, s) + dfs(root.right, s)
   • This sums up all numbers from paths going through the left and right children

Why This Works:

The recursive calls create a tree of execution that mirrors the structure of the binary tree. Each recursive call:

• Maintains its own copy of s (the number built so far)
• Explores all paths beneath the current node
• Returns the sum of all complete numbers found in its subtree

Example Walkthrough:

Consider a simple tree:

    1
   / \
  2   3

• Start with dfs(root=1, s=0)
• Update s = 0 * 10 + 1 = 1
• Not a leaf, so recurse on both children
• Left: dfs(root=2, s=1) → s = 1 * 10 + 2 = 12 → leaf, return 12
• Right: dfs(root=3, s=1) → s = 1 * 10 + 3 = 13 → leaf, return 13
• Total: 12 + 13 = 25

The main function simply initiates the process with dfs(root, 0), starting with an accumulated value of 0.

Example Walkthrough

Let's trace through a concrete example to see how the DFS solution works:

Consider this binary tree:

      4
     / \
    9   0
   / \
  5   1

This tree has three root-to-leaf paths:

• 4 → 9 → 5 forming the number 495
• 4 → 9 → 1 forming the number 491
• 4 → 0 forming the number 40

Step-by-step execution of dfs(root, s):

1. Start at root: dfs(node=4, s=0)

   • Update: s = 0 * 10 + 4 = 4
   • Not a leaf (has children), so recurse on both subtrees

2. Go left: dfs(node=9, s=4)

   • Update: s = 4 * 10 + 9 = 49
   • Not a leaf (has children), so recurse on both subtrees

3. Go left from 9: dfs(node=5, s=49)

   • Update: s = 49 * 10 + 5 = 495
   • This is a leaf! Return 495

4. Backtrack and go right from 9: dfs(node=1, s=49)

   • Update: s = 49 * 10 + 1 = 491
   • This is a leaf! Return 491

5. Back at node 9:

   • Return sum from both children: 495 + 491 = 986

6. Back at root, go right: dfs(node=0, s=4)

   • Update: s = 4 * 10 + 0 = 40
   • This is a leaf! Return 40

7. Back at root:

   • Return sum from both children: 986 + 40 = 1026

Final Answer: 1026

Notice how the parameter s builds up the number as we traverse down each path, and the recursion naturally handles summing all the leaf values. When we backtrack, the previous value of s is restored automatically due to the function call stack, allowing us to correctly build numbers for other paths.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once. At each node, the algorithm performs constant time operations: multiplying by 10, adding the node's value, and checking if it's a leaf node. Since we visit all n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(log n) in the best case (balanced tree), O(n) in the worst case (skewed tree)

The space complexity is determined by the recursive call stack. In the best case scenario where the tree is balanced, the maximum depth of recursion equals the height of the tree, which is O(log n). However, in the worst case where the tree is completely skewed (essentially a linked list), the recursion depth can be O(n). The reference answer assumes a balanced tree scenario with O(log n) space complexity. Additionally, each recursive call uses O(1) extra space for the parameters root and s, which doesn't change the overall space complexity.

Common Pitfalls

1. Modifying the Shared Variable Incorrectly

A common mistake is trying to use a shared variable to accumulate the total sum across all paths, leading to incorrect results due to how the variable is passed or modified.

Incorrect Approach:

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    total_sum = 0  # Trying to accumulate here
  
    def dfs(node, current_number):
        if node is None:
            return
      
        current_number = current_number * 10 + node.val
      
        if node.left is None and node.right is None:
            total_sum += current_number  # ERROR: UnboundLocalError
            return
      
        dfs(node.left, current_number)
        dfs(node.right, current_number)
  
    dfs(root, 0)
    return total_sum

Why it fails: Python treats total_sum as a local variable inside dfs when you try to modify it, causing an UnboundLocalError.

Solution: Use nonlocal keyword or return values properly:

# Option 1: Using nonlocal
def sumNumbers(self, root: Optional[TreeNode]) -> int:
    total_sum = 0
  
    def dfs(node, current_number):
        nonlocal total_sum  # Declare as nonlocal
        if node is None:
            return
      
        current_number = current_number * 10 + node.val
      
        if node.left is None and node.right is None:
            total_sum += current_number
            return
      
        dfs(node.left, current_number)
        dfs(node.right, current_number)
  
    dfs(root, 0)
    return total_sum

# Option 2: Return values (preferred - shown in original solution)

2. Forgetting to Handle Single-Node Trees

Some implementations might incorrectly handle the case where the root itself is a leaf node.

Incorrect Logic:

def dfs(node, current_number):
    if node is None:
        return 0
  
    current_number = current_number * 10 + node.val
  
    # Wrong: assumes every node has at least one child
    left_sum = dfs(node.left, current_number)
    right_sum = dfs(node.right, current_number)
  
    return left_sum + right_sum  # Returns 0 for leaf nodes!

Why it fails: When both recursive calls return 0 (because children are None), the leaf node's value is lost.

Solution: Always check if the current node is a leaf before recursing:

if node.left is None and node.right is None:
    return current_number  # Return the accumulated number for leaf nodes

3. Integer Overflow Concerns

While Python handles arbitrary-precision integers automatically, in other languages or when dealing with very deep trees, overflow might occur.

Potential Issue:

• Very deep trees with all 9s could create numbers exceeding standard integer limits
• Example: A path of twenty 9s would create the number 99,999,999,999,999,999,999

Solution:

• In Python: No action needed due to automatic handling
• In other languages: Use appropriate data types (long long in C++, BigInteger in Java)
• Consider using modulo arithmetic if the problem specifies it

4. Passing Current Number by Reference

Using a list or mutable object to track the current number can lead to unexpected behavior.

Incorrect Approach:

def dfs(node, current_number_list):  # Using list to track number
    if node is None:
        return 0
  
    current_number_list[0] = current_number_list[0] * 10 + node.val
  
    if node.left is None and node.right is None:
        return current_number_list[0]
  
    left = dfs(node.left, current_number_list)
    # current_number_list is modified after left subtree traversal!
    right = dfs(node.right, current_number_list)  # Wrong number passed
  
    return left + right

Why it fails: The mutable list gets modified during the left subtree traversal, so the right subtree receives an incorrect starting number.

Solution: Always pass immutable values (integers) as parameters, letting each recursive call maintain its own copy of the current number.