DEV Community

Akhil
Akhil

Posted on

Sum root to leaf numbers, solving an Amazon interview question

Question : 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.

Eg :

         1
        / \
       2   3
Enter fullscreen mode Exit fullscreen mode

For the tree above,
Path 1 = 1 -> 2 = 12
Path 2 = 1 -> 3 = 13
Output will be 12 + 13 = 25

Just by reading the question, we can say that we've to traverse the tree, but we've to traverse in such a way that the parent -> child relation is maintained.

Depth First Traversal is a type of traversal in which we select a node, and explores as far as possible along each branch before backtracking.

An animation from Wikipedia :
Alt Text

Converting it to code:

   dfs(node){
       if(node == null) return;

       // do something

       dfs(node.left);
       dfs(node.right);
   }
Enter fullscreen mode Exit fullscreen mode

Next is how to process the value at the current node, if we look closely, at each level we're multiplying previous level result by 10 and add the value at the current node level.
Something like this :
Alt Text

  dfs(node,prev){
      if(node == null) return;

      let curr = prev * 10 + node.val;

      dfs(node.left,curr);
      dfs(node.right,curr);
Enter fullscreen mode Exit fullscreen mode

A bit about call stack :

Since here we're recursively calling dfs, for each call a separate call stack is maintained which tracks the root -> current node value and it doesn't interfere with root -> node value of other nodes since they exist in a separate call stack . See animation at the end to understand this better.

The last obstacle is how to return the computed value.

We know that a leaf node is a node whose left and right child are null , that's our clue to return the root -> leaf value for a particular subtree path.

    if(root.left == null && root.right == null) 
       return prev*10 + node.val;
Enter fullscreen mode Exit fullscreen mode

When we come across an internal node, we just add the values returned from the left and right subtrees and return it.

     return dfs(root.left,curr) + return dfs(root.right,curr);
Enter fullscreen mode Exit fullscreen mode

Visualizing each step :
Alt Text

Putting everything together in a code :

var sumNumbers = function(root) {
    return dfs(root,0);
};

function dfs(node,prev){
    if(node == null) return 0;
    if(node.left == null && node.right == null){
        return prev*10 + node.val;
    }

    let curr = prev*10 + node.val;

    return dfs(node.left,curr) + dfs(node.right,curr);
}
Enter fullscreen mode Exit fullscreen mode

I hope you liked my explanation :D

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/rootToleaf.js

Top comments (3)

Collapse
 
namhle profile image
Nam Hoang Le

Can you tell me how to create those GIFs?

Collapse
 
akhilpokle profile image
Akhil
Collapse
 
saravananks profile image
SARAVANAN. K.S

Nice explanation man :)