Uber: Possible path in a binary tree
Problem:
Given a binary tree and an integer k, return whether there exists a root-to-leaf path that sums up to k.
Approach:
Since this is the first problem on this blog, let’s go step-by-step, and work through the solution. This problem is categorized as “easy”, and hence the solution shouldn’t be more than 10–20 lines of code.
Like most binary tree problems, the best approach to the solution must start with thinking about left and right subtrees. For example, let take k=18 and the following binary tree:
8
/ \
4 13
/ \ \
2 6 19A path starting from root can only add up to 18, if any path starting from either left or right subtrees adds up to 18 - 8 = 10 — the problem is now reduced to a recursive problem looking at the left or right subtree. Going one level deeper, A path in the left subtree can add up to 10 if and only if any path in left sub-sub-trees adds up to 10 - 4 = 6. This in essence gives us the 10 line C++ solution to the problem.
First, let’s define our node structure with an integer val, and recursive left- and right- subtrees.
Next, let’s code our recursive solution for path-existence taking care of null subtrees.
There are basically two base cases:
- When the root node itself is null, return false.
- When the root node is a leaf (both left and right are null), simply compare the value of the root to the target.
The recursive case is simply subtracting the root’s value from target, and calling exists_path functions on left/right subtrees with the modified target.
Testing:
Before we go further, I am coming to one of the most important parts of the coding interviews — the one most candidates ignore. Testing. Well-crafted unit tests makes your interview stand out, and might make a difference between a neutral and a strong-hire decision. I am going to use the Gunit testing framework for these blog posts.
Some of the simplest and most obvious test cases are empty/single node trees. Here are 1-line tests for these cases:
A deeper binary tree needs a more elaborate construction. A builder pattern comes in quite handy here. Demonstrating a knowledge of patterns like this also makes your interview stand out. Here is how we can define a builder class for Node:
This allows us to construct the tree in the example above:
Here is how we can write a test using this pattern
Last but not the Least…
Most interviewers follow the initial question with a more advanced version. An advanced version of this question would be: Given a binary tree and an integer k, return a root-to-leaf path that sums up to k. You can use any data structure to return the path.
For the example above, an array with the values starting from the root, e.g. [8, 4, 6] would be an ideal return value.
Always remember that the most advanced problems can be solved by slightly modifying the initial version of the algorithm. If you find yourself writing a new algorithm/code, stop and think! Can you use a standard container to store extra information? Can you cache part of the solution? Can you use an stl:: algorithm?
For the modified problem above, one approach would be to use a std::unordered_map to store the successor relation in the desired path from root to leaf, and to update this map everytime a correct path is found.
Here is the code:
This slightly modified exists_path implementation takes an additional pointer to std::unordered_map and modifies it in recursive call to keep track of the next node in the ideal path. The path itself can be constructed from the table:
Complexity
Most interviews end with analyzing the computational complexity of the algorithm. For this problem, the complexity is simple. We visit every node of the tree once, and perform a constant amount of work for it. As a result, the complexity is O(N), where N is the number of nodes.
