# How to Solve Sum Root to Leaf Numbers

## Sum Root to Leaf Numbers Introduction

The Sum Root to Leaf Numbers problem asks us to return the total sum of all root-to-leaf numbers. This problem requires us to traverse the tree using depth-first search and keep track of the current sum, adding the number from each leaf node we come across.

## Sum Root to Leaf Numbers Problem

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.

### Example Inputs and Outputs

#### Example 1

**Input:** Input: root = [1,2,3]

**Output:** 25

#### Example 2

**Input:** root = [4,9,0,5,1]

**Output:** 1026

## Sum Root to Leaf Numbers Solutions

To solve this problem, we can use a [depth-first search](/content/depth-first-search-interview-questions/index.html) (DFS) approach to traverse the [binary tree](/content/binary-trees-interview-questions/index.html). We can keep track of the current sum, which represents the number that is formed by the path from the root to the current node. If we get to a leaf node, we add the current sum to the total sum. Otherwise, we can [recursively](/content/recursion-interview-questions/index.html) traverse the left and right subtrees, updating the current sum along the way. Finally, we return the total sum as the result.

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

class Solution:
    def sumNumbers(self, root):
        def dfs(node, currSum):
            if not node:
                return 0

# Calculate the current number by appending the node's value to the current sum
            currSum = currSum * 10 + node.val

# If it's a leaf node, return the current number
            if not node.left and not node.right:
                return currSum

# Recursively traverse the left and right subtrees, passing the updated current number
            leftSum = dfs(node.left, currSum)
            rightSum = dfs(node.right, currSum)

# Return the sum of both left and right subtree sums
            return leftSum + rightSum

return dfs(root, 0)

# Create the binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Call the sumNumbers function and print the result
solution = Solution()
result = solution.sumNumbers(root)
print("Sum of numbers in the binary tree:", result)
```

#### Time/Space Complexity Analysis

- Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the depth-first search traversal.
- Space Complexity: O(H), where H is the height of the binary tree. In the worst case, the recursion stack can grow up to the height of the tree.