# Sum Root to Leaf Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-root-to-leaf-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sum-root-to-leaf-numbers
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow), [Visa](https://scaleengineer.com/companies/visa)
---
## 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.

A **leaf** node is a node with no children.

**Example 1:**

![](https://assets.glich.co/dsa/sum-root-to-leaf-numbers/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/sum-root-to-leaf-numbers/image1.jpg) 

**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`.

# Approaches
## Brute Force: Generate All Paths and Sum
This approach first generates all root-to-leaf paths, stores them, and then iterates through these paths to calculate the corresponding numbers and their sum. It's straightforward but inefficient due to high space usage.
**Time:** O(N*H) · **Space:** O(N*H)
**Pros:** The logic is separated into two clear, understandable steps: finding paths and then summing them.; It's a direct translation of the problem statement.
**Cons:** Very inefficient in terms of space. It requires storing all root-to-leaf paths, which can be memory-intensive for large trees.; The time complexity is also suboptimal due to the overhead of creating and storing path strings/lists and then iterating over them again.
### Explanation
The core idea is to separate the problem into two distinct steps: path finding and summation.

1.  **Path Finding**: A Depth-First Search (DFS) traversal is used to find all paths from the root to every leaf node. We use a helper function that maintains the current path from the root. When a leaf is encountered, the current path is complete and is added to a list of all paths.

2.  **Summation**: After the traversal is complete, we have a list of all paths (where each path is a list of digits). We iterate through this list. For each path, we convert the sequence of digits into an integer. For example, the path `[4, 9, 5]` is converted to the number 495. These numbers are then added to a running total.

Here is a code snippet illustrating this approach:
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int sumNumbers(TreeNode root) {
        List<String> allPaths = new ArrayList<>();
        findPaths(root, "", allPaths);
        
        int totalSum = 0;
        for (String path : allPaths) {
            totalSum += Integer.parseInt(path);
        }
        return totalSum;
    }
    
    private void findPaths(TreeNode node, String currentPath, List<String> allPaths) {
        if (node == null) {
            return;
        }
        
        currentPath += node.val;
        
        if (node.left == null && node.right == null) {
            allPaths.add(currentPath);
            return;
        }
        
        findPaths(node.left, currentPath, allPaths);
        findPaths(node.right, currentPath, allPaths);
    }
}
```
### Algorithm
1. Initialize an empty list, `allPaths`, to store string representations of the numbers for each root-to-leaf path.
2. Define a recursive helper function `findPaths(node, currentPathString, allPaths)`.
3. In the helper function, if the current `node` is null, return.
4. Append the current node's value to `currentPathString`.
5. If the current `node` is a leaf (both left and right children are null), add the `currentPathString` to the `allPaths` list.
6. Recursively call the helper function for the left and right children.
7. After the initial call to `findPaths` on the root completes, iterate through `allPaths`.
8. For each string in `allPaths`, convert it to an integer and add it to a `totalSum`.
9. Return `totalSum`.

## Optimal Approach: Recursive DFS (Pre-order Traversal)
A much more efficient solution involves calculating the path numbers on-the-fly during a single Depth-First Search (DFS) traversal. This avoids the overhead of storing all paths, leading to optimal time and space complexity.
**Time:** O(N) · **Space:** O(H)
**Pros:** Optimal time complexity as it visits each node only once.; Optimal space complexity, using space proportional to the tree's height for the recursion stack.; Elegant and concise solution.
**Cons:** On extremely deep trees (not applicable with this problem's constraints), deep recursion could potentially lead to a stack overflow error.
### Explanation
This approach uses a pre-order traversal pattern. We maintain the numerical value of the path from the root to the current node's parent. As we descend to a child node, we update this value.

The formula to update the number at each step is `newNumber = currentNumber * 10 + node.val`. For example, if we are at node `9` and the path from the root was `4`, the `currentNumber` passed to `9` would be `4`. The new number becomes `4 * 10 + 9 = 49`.

When we reach a leaf node, the number formed along that path is complete. We return this number. For non-leaf nodes, we recursively call the function for the left and right children and sum their results. This effectively sums up all the numbers from all leaf nodes below.

Here is the implementation:
```java
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }

        currentSum = currentSum * 10 + node.val;

        if (node.left == null && node.right == null) {
            return currentSum;
        }

        int leftSum = dfs(node.left, currentSum);
        int rightSum = dfs(node.right, currentSum);

        return leftSum + rightSum;
    }
}
```
### Algorithm
1. Define a recursive helper function, `dfs(node, currentSum)`, which returns the sum of numbers for the subtree rooted at `node`.
2. The `currentSum` parameter holds the numerical value of the path from the root to the parent of `node`.
3. Base Case: If `node` is null, it contributes nothing to the sum, so return 0.
4. Update the sum for the current path: `currentSum = currentSum * 10 + node.val`.
5. Leaf Node Check: If the current `node` is a leaf (both children are null), it signifies the end of a path. Return the `currentSum`.
6. Recursive Step: If it's not a leaf, recursively call `dfs` for the left and right children with the updated `currentSum`. Return the sum of the results from these two calls: `dfs(node.left, currentSum) + dfs(node.right, currentSum)`.
7. The main function initiates the process by calling `dfs(root, 0)`.

## Optimal Approach: Iterative DFS with a Stack
This is an iterative counterpart to the recursive DFS solution. It uses an explicit stack to manage the traversal, achieving the same optimal performance while being immune to recursion depth limits.
**Time:** O(N) · **Space:** O(H) on average, O(N) in the worst case
**Pros:** Avoids recursion, thus preventing stack overflow errors on very deep trees.; Maintains the same optimal O(N) time complexity as the recursive solution.
**Cons:** The code can be slightly more verbose and less intuitive than the recursive version.; Worst-case space complexity can be O(N) for a wide, complete tree, whereas the recursive version's space is always bounded by the tree's height O(H).
### Explanation
Instead of relying on the call stack for recursion, we use our own stack. The stack will store pairs of `(TreeNode, currentNumber)`.

We start by pushing the root node and an initial number 0 onto the stack. The main loop continues as long as the stack is not empty. In each iteration, we pop a node and its corresponding path number. We calculate the new number for the path ending at this node. If the node is a leaf, we add this number to our total sum. Otherwise, we push its children (if they exist) onto the stack, along with the new path number. To maintain the pre-order traversal logic (process node, then left, then right), we push the right child onto the stack before the left child.

Here is the implementation:
```java
import java.util.Stack;

// Helper class to store a node and the sum up to it.
class Pair {
    TreeNode node;
    int val;
    Pair(TreeNode node, int val) {
        this.node = node;
        this.val = val;
    }
}

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        
        int totalSum = 0;
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root, 0));
        
        while (!stack.isEmpty()) {
            Pair current = stack.pop();
            TreeNode node = current.node;
            int currentSum = current.val;
            
            currentSum = currentSum * 10 + node.val;
            
            if (node.left == null && node.right == null) {
                totalSum += currentSum;
            }
            
            if (node.right != null) {
                stack.push(new Pair(node.right, currentSum));
            }
            if (node.left != null) {
                stack.push(new Pair(node.left, currentSum));
            }
        }
        return totalSum;
    }
}
```
### Algorithm
1. If the root is null, return 0.
2. Initialize `totalSum = 0`.
3. Create a stack to store pairs of `(TreeNode, currentNumber)`.
4. Push the initial pair `(root, 0)` onto the stack.
5. Loop while the stack is not empty:
   - Pop a pair `(node, number)` from the stack.
   - Calculate the new number for the path to this node: `newNumber = number * 10 + node.val`.
   - If `node` is a leaf, add `newNumber` to `totalSum`.
   - If `node` has a right child, push `(node.right, newNumber)` to the stack.
   - If `node` has a left child, push `(node.left, newNumber)` to the stack.
6. Return `totalSum`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int sumNumbers ( TreeNode root ) { return dfs ( root , 0 ); } private int dfs ( TreeNode root , int s ) { if ( root == null ) { return 0 ; } s = s * 10 + root . val ; if ( root . left == null && root . right == null ) { return s ; } return dfs ( root . left , s ) + dfs ( root . right , s ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var sumNumbers =
  function (root) {
    function dfs(root, s) {
      if (!root) return 0;
      s = s * 10 + root.val;
      if (!root.left && !root.right) return s;
      return dfs(root.left, s) + dfs(root.right, s);
    }
    return dfs(root, 0);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int sumNumbers ( TreeNode * root ) { function < int ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int s ) -> int { if ( ! root ) return 0 ; s = s * 10 + root -> val ; if ( ! root -> left && ! root -> right ) return s ; return dfs ( root -> left , s ) + dfs ( root -> right , s ); }; return dfs ( root , 0 ); } };
```

### Python

```python
# Definition for a binary tree node. # 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 : Optional [ TreeNode ]) -> int : def dfs ( root , s ): if root is None : return 0 s = s * 10 + root . val if root . left is None and root . right is None : return s return dfs ( root . left , s ) + dfs ( root . right , s ) return dfs ( root , 0 )
```