Sum Root to Leaf Numbers

Hi Geeks! Welcome to 100 Days of Leetcode Programming Challenge.

Day 46

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.

Note: A leaf is a node with no children.

Example:

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.

Solution

Naive Approach

When I look at this problem, the first solution came to my mind is below approach.

  1. In this approach, we store all the Paths in list.
  2. Once we store all the paths in list, we start to execute its total sum.

C# Program

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int SumNumbers(TreeNode root) {
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        List<string> list = new List<string>();
        Helper(root,sb,list);
        foreach(string s in list)
            sum += int.Parse(s);
        return sum;
    }
    public void Helper(TreeNode root,StringBuilder sb, List<string> list)
    {
        if(root == null){
            return;
        }
        int len = sb.Length;
        sb.Append(root.val);
        if(root.left == null && root.right == null){
            list.Add(sb.ToString());
        }
        if(root.left != null){
            Helper(root.left,sb,list);
        }
        if(root.right != null){
            Helper(root.right,sb,list);
        }
        sb.Length = len;
    }
}

Even though, its looks traditional and accepted in Leetcode.

Here, you can see unnecessary steps. To just calculate sum, we are storing all paths. We don’t want to store all paths, then how can we reduce that. See my below improved approach.

It looks simple and efficient.

DFS is on fire

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int SumNumbers(TreeNode root) {
        return DFS(root,0);
    }
    
    public int DFS(TreeNode root,int currentSum){
        
        if(root == null)
            return 0;
        
        currentSum = currentSum * 10 + root.val;
        
        if(root.left == null && root.right == null)
            return currentSum;
        
        int leftSum = DFS(root.left,currentSum);
        
        int rightSum = DFS(root.right,currentSum);
        
        return leftSum + rightSum;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s