Tech interview question — binary trees

Binary tree is the most favoured topic when it comes to tech interviews.

Here is a real interview question, and how to approach it.

Question: Given a Binary Tree, If I start drawing vertical lines through the Nodes of the tree — find the Nodes falling on the same vertical line, from leftmost to rightmost line.

In the diagram below the expected output would be [4], [2,9], [1,5,6], [3,8], [7]

First things first: do not jump to a solution yet. Think through, and ask questions. Read more about how to ask the right questions here.

Here is a possible solution.

Start at the root node with line number as zero. As you move left decrement the line number by 1 and as you move right increment the line number by 1.

Keep a HashMap<Integer, List<Node>> where key is the line number and value is the list of nodes falling on the line. As you traverse the tree you keep adding nodes to the map in respective list.

At the end, you have List of nodes for each line number that you can print. For extra credit you would also mention that you can do this in O(n).

We, however missed the fact that the nodes need to be printed from left line to right line. And since we are using a HashMap that doesn’t give elements in an ordered way, our output wont be as expected.

To solve this, you could either use a TreeMap and sort it. This however increases the complexity.

Or you could use the minimum and maximum values of line number and just iterate from min to max and print the line numbers. This means we would be able to do it in O(m) — m being the number of lines, in addition to O(n) which is the tree traversal time.

It is always more than just a tree

Depending on the level of experience and what the interviewer is looking for expect some follow up questions as well.

• What is the space complexity of your solution? As you are storing all the nodes of the tree its essentially O(n).
• What if this tree is very large and doesn’t fit in memory? Think about how to partially load the tree in memory.
• What are the different traversal algorithm you would choose to traverse the tree and why? Think of in-order, pre-order or post-order traversals.
• Does having a balance tree simplify the solution?
• What is the worst case scenario of the solution?

For extra credits think of how your algorithm is going to work for some of the trees like given below.

Hope this helps in approaching problems related to binary trees in interviews.

Got a challenge for us ?

Do you have a question that you got asked in an interview and still wondering what would have been the best approach to solve it ? Challenge us and we will get back to you.

Email us at: developers@interviewparrot.com