# 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

## More from CppCodingZen

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