A common question for job interviews is searching in trees and therefore you should always be prepared to solve this with ease.

As always then solving a problem you want to solve it conceptually before writing the actual code. This is done by going through the logical steps needed to get the desired outcome for one specific case. When this case works, you test your conceptual solution with other inputs and expectations. If it still works you can now proceed to convert this logic into code.

The first step when converting the logic to code is to write up the logical steps as comments, aka pseudocode. When this pseudocode is written you can now proceed to convert this to real code.

Now we convert the pseudocode to real code. Before writing the code you should have a clear sense of which data structures and algorithms this solution appeals to. We want to keep the code performant and clean so we are doing ongoing refactoring as we write the code.

You might see that this approach resembles the prototyping approach where you are first to solve the problem fast in an abstract way, which will provide you with fast feedback and a good overview, and when a viable solution is found you start to implement the details.

Using the three-step process to solve a tree-search question

Let’s consider the following question:

Write an algorithm to check if an object contains a given value.

To solve this we are going through the three-step process:

1. Solve the question conceptually
2. Write the pseudocode
3. Write the code

1) Solving the question conceptually

By looking at this problem conceptually we start with setting up some test input and use it to assert it will give an expected result. This is like doing test-driven development conceptually!

Now we know where we are coming from and what the end result should be for two cases.

Next, let’s consider the logical steps to complete for these two tests to return the expected value:

1. Check if the provided object equals the expected value
2. If it does, return true
   1. else go through every child and repeat from step 1
3. Return false as default if no matching value is found

Having these logical steps in place gives us a clear overview of the algorithm and provides us with a solid skeleton which helps us get the code right on the first attempt.

2) Writing the pseudocode

Let’s write up the logical steps from the conceptual solution as pseudocode:

This is all pretty simple. That’s why this approach works!

Next step is actually writing the implementation code.

3) Converting pseudocode to real code

If the two previous steps are done correctly and you are familiar with javascript this should be the easiest step, as you are simply being a code monkey here.

That being said there is some basic data structure and algorithm theory related to this question that your interviewer is testing you in. When looking at these logical steps it is clear that we are dealing with a recursion/loops solution.

For this question, the interviewer is testing you in trees (the data structure) and tree traversal algorithms. If you have a computer science background you know that there are a depth-first and a breadth-first search algorithm.

Depth-first will traverse as deep as possible before moving on and breadth-first will go as breadth as possible by traverse all children before moving on.

Let’s look at how to implement these algorithms with javascript.

Depth-first tree traversal

For depth-first tree traversal, you need a stack to traverse down the tree of nodes. For this reason, you can use the built stack in the javascript runtime by using recursion or you can implement your own stack and use a while loop.

Depth-first tree traversal with recursion

The solution for depth-first search with recursion looks like this:

This solution is shorter than the non-recursive because it doesn’t need to implement a stack. When you do recursion the method being called will be added to the top of the execution stack in the javascript runtime. The downside is that recursion can be harder to understand and might make the code flow harder to follow.

The non-recursive depth-first search looks like this:

As you see, slightly more code is needed here when you are implementing the stack yourself. The stack is implemented using shift and unshift and a while loop is looping through the stack. For every value, it will check if the value matches the value to search for and if not, it will add all it’s children to that stack.

Breadth-first tree traversal

The breadth-first tree traversal uses a queue to hold the nodes to traverse. This ensures that all children will be traversed before moving on.

For each loop the first element from the queue will be evaluated and if no match it will try to traverse the children. For each child, it will push to the queue.

Breadth-first search vs depth-first search, which is best?

If you prefer the shortest possible solution, then recursive depth-first is your choice. If not, there is no performance benefit when the tree is unknown, as you have no clue knowing which algorithm will traverse the wanted node first. The question is simply if you should use a stack or a queue.

Conclusion

This post showed you how to use my three-step interview approach to find a nested value in a tree-like object.

This got solved using the following approach: solve it conceptually, solve it with pseudocode and solve it with real code. We ended up with multiple possible implementations of this solution using recursive depth-first search, non-recursive depth-first search, and non-recursive breadth-first search.

If you liked this post make sure to comment, share and subscribe.

If you are looking to prepare for an Angular job interview and want help landing your dream job, feel free to contact me and I will see how I can help you. Having done this many times myself successfully and being able to get much higher paying jobs than my peers, I’m sure I can help you.