# 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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/sum-root-to-leaf-numbers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.