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

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 :

Converting it to code:

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

       // do something

       dfs(node.left);
       dfs(node.right);
   }

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 :

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

      let curr = prev * 10 + node.val;

      dfs(node.left,curr);
      dfs(node.right,curr);

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;

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);

Visualizing each step :

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);
}

I hope you liked my explanation :D

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

Comments

[Nam Hoang Le]

Can you tell me how to create those GIFs?

[Akhil]

This tool : dai-shi.github.io/excalidraw-claym...

[SARAVANAN. K.S]

Nice explanation man :)