Uber: Possible path in a binary tree

Problem:

Approach:

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 19

A 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:

  1. When the root node itself is null, return false.
  2. 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:

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…

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

Solutions to programming interview questions at some of the top companies in the world: cppcodingzen.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store