Sum Root To Leaf Numbers - Leetcode Solution

The problem statement is:

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 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, the sum is 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, the sum is 495 + 491 + 40 = 1026.

Approach:

The problem can be solved by traversing the tree in a depth-first manner. We can keep track of the current number formed by adding the current node’s value to the number so far. If the current node is a leaf, we can add the current number to the total sum. Otherwise, we can recursively traverse the node’s left and right children, passing the current number as an argument.

Algorithm:

• Initialize a global variable sum and set it to 0.
• Define a helper function named dfs with parameters root and num.
• If root is null, return.
• If root is a leaf, add the current num to the sum by sum = sum + num*10 + root.val.
• Recursively call the dfs function for the left and right children of root, passing num*10+root.val as the updated value of num.
• Finally, call the dfs function for the root node with num = 0 to start the traversal from the root node.
• Return the sum.

Code:

class Solution { int sum = 0; // global variable to store sum public int sumNumbers(TreeNode root) { dfs(root, 0); // calling helper function with root and initial num as 0 return sum; }

public void dfs(TreeNode root, int num){
    if(root == null){
        return;
    }
    if(root.left==null && root.right==null){ // checking if node is leaf
        sum += (num*10) + root.val; // adding the current num to the sum
        return;
    }
    dfs(root.left, num*10 + root.val); //recursive call for left child
    dfs(root.right, num*10 + root.val); //recursive call for right child
}

}

Time Complexity: The time complexity of the above algorithm is O(N), where N is the total number of nodes in the tree. This is because we are visiting each node once.

Space Complexity: The space complexity of the above algorithm is O(H), where H is the height of the tree. This is because the maximum number of recursive calls at any given time is equal to the height of the tree.

1