# 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)`