xmas

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, I’ll mainly discuss how to analyze a tree problem step by step with a popular question. I’ll 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 haven’t solved this problem before, do spend a couple of minutes thinking about it.

 

Traverse tree

It shouldn’t be hard for you to realize that the root of this question is to traverse a tree. More specifically, it’s 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. It’s worth to note that it makes no difference whether it’s a binary tree or not.

I’ll 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 node’s 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. I’ll 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, we’ll 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 it’s 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.

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook8Tweet about this on TwitterShare on LinkedIn14Share on Reddit1

3 thoughts on “Uber Interview Questions – Deepest Node In a Tree

  1. Hi,

    Nice post! But your recursive solution is still a DFS, instead of BFS.

    def deepest_leaf(root, depth):

    for child in root.children:
    deepest_node, depth = deepest_leaf(child, depth+1)

    In order to get a returned value from a child, we have to dive deep first.

    For BFS, it’s better to write in a non-recursive way with using a queue.

    Cheers

    1. The recursive solution has to be DFS, recursion by definition means you are going to keep diving in. Please note that the author does not claim to be implementing BFS by recursion. They are just trying to discuss different ways of attacking the problem 🙂

  2. Iterative solution based on BFS search, deepest is last element in left in the queue.

    void tree::finddeepest(node *root, int &deepest)
    {
    queue q;
    if(root== NULL)
    return;
    q.push(root);
    while(!q.empty())
    {
    node *temp = q.front();
    deepest = temp->data;
    node *left = temp->left;
    node *right = temp->right;
    q.pop();
    if(left!=NULL)
    q.push(left);
    if(right!=NULL)
    q.push(right);
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *