Uber Interview Questions - Deepest Node In a Tree

Uber Interview Questions - Deepest Node In a Tree Tree problem is also one of the most commonly asked coding interview questions. Some people might be afraid of tree at first. However, most tree problems in coding interviews are quite straightforward given that there are not too many operations. As a result, if you are familiar with basic concepts like BST and how to traverse a tree, you are already half done. What you need next is just more practice. From this post, Ill mainly discuss how to analyze a tree problem step by step with a popular question. Ill also summarize some commonly used techniques that can be adapted to other problems as well. Problem How to find the deepest node in a tree? Several reasons this question is selected here: Recently it has been asked multiple times at Uber. There are many other related problems. Many basic concepts are also covered in this question as well. If you havent solved this problem before, do spend a couple of minutes thinking about it. Traverse tree It shouldnt be hard for you to realize that the root of this question is to traverse a tree. More specifically, its a BFS (Breadth-first search) problem. Imagine that if you can traverse the tree by level (BFS), the last node visited is the deepest node. Its worth to note that it makes no difference whether its a binary tree or not. Ill briefly explain the details here. To BFS traverse a tree, you need to keep a queue that stores nodes waiting for being visited. Initially, the queue only contains root node. So every time we pop one node from the queue, after visiting this node, add all its children to the queue. By repeating this process, we are traversing the tree by level order and when the queue gets empty, the last node is the deepest one. Recursive solution When comes to tree problem, recursion should be something you think about. If this problem can be solved by the results of sub-problems, then recursion can definitely be used. More specifically, if we know the result of all the children, can we easily get the result of the root node? Suppose we know the deepest node for each sub-tree of the root nodes children, we are still not sure which one is deeper. However, if we can also know the level of each candidate, the answer is clear. So we can summarize our approach here now: the recursion function takes a tree node as input and returns the deepest node of this tree with its level. For the root node, we use this function to check each of its children and for all the returned nodes, we select the one with the largest level. Then return this node with (level + 1). If you are confused by returning two values, let me provide several solutions. If you are using Python, then you can just do that as the language support this. If you are using C++, you can select one returned value to be a pointer parameter. Another way to do that is to define a class/struct that only contains this two values and use it as the return value. Extensions As I mentioned earlier, there are just so many problems that are relevant to this one. Ill list several popular ones here: Find the height of a tree. This can also be solved both recursively or non-recursively. Find the longest path from the root to leaf in a tree. Find the deepest left leaf of a tree. Takeaways Again, well summarize some techniques that can be used in other problems. Traverse tree by level and BFS. Whenever you need to traverse a tree by level, BFS should the first thing in your mind. There are many interview questions that require this technique, e.g. print tree by level. Recursion is common for tree problem. Whenever you notice that the subtree problem can be used to solve the whole problem, you should try recursion (this might not be the optimal solution, but its worth to try). When you need a function to return two values, you should not be confused about how to do that. One homework is to analyze the time and space complexity of this problem. If you have trouble, just shoot us an email at info@gainlo.co.