> For the complete documentation index, see [llms.txt](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/sum-root-to-leaf-numbers.md).

# Sum Root to Leaf Numbers

## Problem Statement

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

{% hint style="info" %}
Note:

A leaf is a node with no children.
{% endhint %}

## Testcases

```
Example 1:

Input: [1,2,3]
    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:

Input: [4,9,0,5,1]
    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.
```

## Prerequisite Knowledge

### Depth-First-Search

Refer to the *Prerequisite Knowledge* section in **Surrounded Regions**:

{% content-ref url="/pages/-MA26JNnWd1vd4oJP-Lr" %}
[Surrounded Regions](/june-leetcoding-challenge/week-3/surrounded-regions.md)
{% endcontent-ref %}

## Algorithm

### Depth-First-Search Approach

1. Traverse through each branch of the tree and iteratively construct the number that it forms until the branch ends.
2. If the branch ends, add the value to the cumulative sum, stored in a global variable.
3. If the tree reaches the last leaf node, stop the process and return the sum value.

## Code

{% code title="DFS Helper Function" %}

```cpp
int sum = 0;
void DFS(TreeNode *&node, int currentSum) {
    // Tree is empty
    if(!node) {
        return;
    }
    // Construct the number from the node elements of each branch
    currentSum = (currentSum * 10) + node->val;
    // If the branch ends, add the value to the cumulative sum
    if(!node->left && !node->right) {
        sum += currentSum;
    }
    // Traverse the left branch
    if(node->left) {
        DFS(node->left, currentSum);
    }
    // Traverse the right branch
    if(node->right) {
        DFS(node->right, currentSum);
    }
}
```

{% endcode %}

{% code title="Sum Numbers Function" %}

```cpp
int sumNumbers(TreeNode* root) {
    // Begin the DFS traversal at the root node with an initial sum value of 0
    DFS(root, 0);
    return sum;
}
```

{% endcode %}