Coding Interviews: Solving the “Sum Tree Branches From Root to Leaf” Problem

A General Note about Coding Interviews

These coding interview algorithm problems aren’t necessarily the best reflection of how you’ll perform at your job or in college, but more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

Glassdoor

Asked by: Facebook

Problem Description

Return a list of root-to-leaf sums (left to right) from a given tree.

An example of an integer tree and its corresponding list of sums

Problem Solution

Let’s illustrate the steps we’ll take in our algorithm in order to help build a strong mental model. We will traverse through the tree from left to right, starting at the root node. Each path during the traversal may only “pass through” one node on each “level” of the tree.

An example of the traversal paths to collect all root-to-node sums.

Now let’s examine the code. Firstly, I created a Node function to help us repeatably build tree nodes while testing. You could and should write your own tests to confirm your solution.

A recursive solution to traverse through an integer tree.

1. In this solution, we use recursion to traverse through each node of the tree. When we recurse, we are homing in on some criteria with each successive invocation of our function. In our problem, as with a lot of tree problems, our termination criteria is whether or not we have any more nodes to traverse through along that branch. This criterion can be seen on line 2.
2. Our recursive case can be seen in the else statement from lines 4 through 14. Here, we iterate through all of the children, recursively call getRootToLeafSums with the current child, and add the current node’s value to the child sum produced from our recursive call.
3. In both the base case and recursive case, we return an array of numbers. When working through recursive problems, it can often be useful to first layout out your function skeleton and conditional statement(s). After that, identifying the JavaScript “type” or data structure that is returned can be very illuminating. You know that every call of getRootToLeafSums needs to return an array of numbers, therefore, you know that your base case and recursive case both need to return that same data structure.

And that’s it! The bulk of this problem is deciding how to traverse the tree structure and how to terminate your traversals through each branch. The math portion of this problem is fairly trivial.

Conclusion

Often, these problem solutions aren’t very verbose. The key is to map out your traversal and have a proper understanding of the underlying data structures.