tumblr_nnmrdskJiY1qfirfao1_1280

Second Largest Element of a Binary Search Tree

Over the past several weeks, many of our users suggested us cover some questions about BST (Binary search tree) as they’ve been asked about this recently.

BST is a very good data structure to ask in coding interviews. Here are the reasons:

  • BST is a widely used data structure and it’s important to know it.
  • It’s neither too complicated nor too simple to ask in a coding interview.
  • Many concepts like traversing, recursion can be covered with BST related questions.

This post will cover topics like BST, recursion and some tips about coding as well.

 

Question

Given a BST (Binary search tree), find the second largest element of it.

I won’t further explain the question since it’s very straightforward. It’s also worth to mention that this question has been asked by companies including Microsoft, Google, Facebook and so on recently.

 

Analysis

Unlike some array related interview questions, tree questions usually require some basic knowledge to solve. If this is the first time for you to know BST, I highly recommend you go check the definition and related operations of BST before moving on to the rest of this post.

More specifically, you are expected to know the following concepts:

  • What a BST is and how BST is different from hash when doing the lookup.
  • How to insert, lookup, delete a node from a BST and the corresponding time complexity.
  • How to traverse a BST.

If you are quite familiar with all of these, you should be able to come up with this very straightforward solution: First, find the largest element of the BST and delete it. Then, find the largest element of the current BST, which is the 2nd largest element of the original BST. Apparently, this is not efficient and I’ll cover the better solution next.

 

Recursion

If you have read our previous post about tree problem, you should know that recursion is an extremely common technique to solve tree related question. The idea is very simple, by solving the subproblem from the left and right subtree, we can combine these two results with the root node to solve the whole problem.

Another thing you should think about is that in order traversal of a BST will return all the elements in order. This is not something fancy, you should just know it since it’s one of the fundamental concepts of BST.

By combining the above analysis, we have the following solution:

  • Do the in order traversal of the given BST.
  • Keep track of the index of each visited element and when it’s the 2nd one, output as the 2nd largest element.

As you can see, the solution doesn’t come from nowhere and I’d like to illustrate how to get the solution step by step, which is the whole point of this post. If you find it hard to implement the code, don’t worry since we’ll provide some tips soon.

 

Follow-up

What if we want to get the k-th largest element of the BST?

You can see that the above in-order traversal solution can easily be extended to get the k-th largest element and all we need to do is to output the k-th visited element instead of the second. In addition, I hope you can come up with this follow-up question in preparation. By removing or generalizing particular conditions, the question can be much more interesting.

Some people also find it hard to implement the code, I’ll provide few tips here:

  • You don’t need to store all the visited elements into an array and find the k-th element. Instead, use a global variable i to record the index of visited elements. Inside the traversal function, every time when you visit an element, just increment i by one and when i == k, output the current element.
  • Be careful about cases where there are less than k elements in the BST.
  • You should handle empty tree as well.
  • Don’t forget to check if left and right are null when traversing the tree.

 

Takeaways

Tree problems are usually easier since there are many techniques can be re-used to solve other similar questions. Some takeaways include:

  • Be very familiar with basic concepts/operations of BST, especially the time complexity and pros and cons when comparing with other data structures.
  • In-order traversal will give you all elements in order.
  • You should definitely consider recursion when solving tree related problems. It may not work for all questions, but it’s an extremely common techniques and can make your code concise.

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 Facebook4Tweet about this on TwitterShare on LinkedIn0Share on Reddit0

8 thoughts on “Second Largest Element of a Binary Search Tree

  1. I think there is a logical fallacy in the solution. Shouldn’t it be “reverse” in-order traversal since we are interested in finding the K-th largest and not the K-th smallest?

    1. Hi Balaji,

      You are correct. Thanks for pointing out. But no matter if it’s biggest or smallest, the solution can easily be adjusted.

  2. This is not clear at all.
    Do the in order traversal of the given BST.
    Keep track of the index of each visited element and when it’s the 2nd one, output as the 2nd largest element.

    2nd largest element is the parent of the right most node of the BST. What do you mean by “when it’s the 2nd one, output as the 2nd largest element.”? Do you mean the 2nd visited element? That will be the 2nd smallest element. The question is about 2nd largest element. Please let me know if I am wrong.

    1. Hi Harish,

      let me clarify. It should be the last but 2nd element that you visited. The core idea is that keep track of the index of element you’ve visited, then you have the full control over which one you want to output.

  3. I think the solution that you suggested is O(n), whereas this can be solved in O(lg n), provided the tree is balanced. Finding the largest element is O(lg n).

    If the largest node has children, the second largest node is the rightmost node of the left subtree O(lg n).

    Otherwise, if the largest element is not root, the second largest is its parent O(1).

    1. The inorder traverse ( traverse to the largest, then to the 2nd largest) has the same time complexity as the way you suggested : find the last node, then find the 2nd , either the parent of the right most node of the left subtree,
      The nodes visit sequence is the same.

  4. Why not just find the predecessor of the largest node?

    – If root has right child, then keep moving right while keeping track of the previous node.

    – If root has no right child, then find the largest element in the root’s left subtree.

    Time complexity O(log n) assuming the tree is height balanced.

  5. if anyone needs below is the java implementation just call it as tree.findKthBiggestElement(root, new Stack(), 6) if you want the 6th element to be returned
    Hoping below java implementation might help somebody to understand. Let me know if you see any issues.


    Node findKthBiggestElement(Node node,Stack stack,int order){
    if(node == null){
    return null;
    }
    Node right = findKthBiggestElement(node.right, stack, order);
    if(right != null){
    return right;
    }
    stack.push(node);
    if(stack.size() == order){
    return node;
    }
    Node left = findKthBiggestElement(node.left, stack, order);
    if(left != null){
    return left;
    }
    return null;
    }

Leave a Reply

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