In our previous posts, we’ve covered quite a few coding interview questions about string. This time, I’d like to analyze a binary tree problem.
In my opinion, most interview questions about data structures like binary tree, linked list are relatively easier because these data structures have limited ways of operation so that it can’t be too flexible. In other words, with enough practice, you should be able to be familiar with these topics. We’ll explain more soon.
In this post, I’ll mostly focus on topics including tree traversal, recursion and deeper analysis of these two concepts. Again, the goal is not to give you something like a standard answer, but help you be able to solve other problems with similar techniques.
Given a binary tree, print all of the paths from the root to leaf nodes.
Let me give you an example.
For the above binary tree, we should print the following paths:
This question was recently asked by Facebook.
Obviously, this is a tree traversal problem, which is quite common in coding interviews. You’d better be extremely familiar with algorithms like in-order, pre-order, post-order traversal, DFS, BFS etc..
In this problem, you can notice that the traversal order is to go deeper and deeper from each node and when it hits the leaf, it will go back and go deeper again. I would expect Depth-first search (DFS) to come to your mind immediately. In fact, the common mental model is that by analyzing the nature of the traverse problem, we come to DFS, instead of the other way around – try all the traversal algorithms to see which works.
We all know that DFS has two ways to implement – recursive approach and non-recursive approach. The recursive version is usually easier to write. You first check the root node and then traverse the two subtrees separately. Since you need to print all the paths, you can pass all the nodes that have traversed to the function. So the high level pseudo code is like this:
I ignored all the detailed checkings to it easier to understand. When it hits the leaf node, you can just print the current node and everything in previous_nodes in reverse order.
When I was an interviewer, I may ask candidates to implement non-recursive version to test his/her coding skills. A common technique here is to use stack for non-recursive solution.
It works as follow:
- After visiting a node, we put the left child (or the right child if left doesn’t exist) into the stack.
- Repeat step 1 until we hit the leaf node.
- Once we hit the leaf, just print everything in the stack. Then pop the leaf node from the stack, repeat from step 1 (the current node is the top of stack)
It’s an extremely common topic to compare recursive and non-recursive solution. In essence, they are the same since recursion will still need to store all the variable in a stack internally.
It’s hard to compare which one is better since it’s always case by case. Usually they have similar performance. Recursion usually makes the program shorter and cleaner, while iterative approach is easier to understand from the program perspective. In addition, without storing the temporary result, recursive approach can be most costly sometimes (e.g. Fibonacci problem).
To summarize techniques we used in this coding interview question:
- It’s better to be familiar with all common tree traversal algorithms.
- When the traversal order is vertical instead of horizontal, we should think about DFS.
- Recursive and non-recursive solution for DFS.
- Recursion vs non-recursion.