# How to count sum for root to leaf numbers

Given a `binary tree`

, each node has a value `from 0 to 9`

. Each path from a `root to a leaf`

represents a `number,`

return a `sum`

of all these `numbers`

`Example 1`

```
Input: 1
/ \
5 4
Output: 29
```

Explanation:

`1 -> 5`

= 15,`1 -> 4`

= 14, 15 + 14 = 29

`Example 2`

```
Input: 1
/ \
2 3
/ /
4 5
/ \
6 0
Output: 2830
```

Explanation:

`1 -> 2 -> 4`

= 124,`1 -> 3 -> 5 -> 6`

= 1356,`1 -> 3 -> 5 -> 0`

= 1350

## Algorithm

Let's see one example in details and try to find out the algorithm to solve this problem

This binary tree has two paths:

`1 -> 2 -> 4`

=`124`

`1 -> 5`

=`15`

Let's see how can we get `124`

. On level 1 there is `1`

, on the level `2`

- `12`

, on the level `3`

- `124`

. On each level, we multiply the previous number on `10`

and add the node's value.

## Code

```
public int SumNumbers(TreeNode root)
{
return SumNumbers(root, 0);
}
private static int SumNumbers(TreeNode root, int sum)
{
if (root == null)
{
return 0;
}
sum = sum * 10 + root.Value;
if (root.Left == null && root.Right == null)
{
return sum;
}
return SumNumbers(root.Left, sum) + SumNumbers(root.Right, sum);
}
```

**Time Complexity**: `O(n)`