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)