Second Largest Element of a Binary Search Tree

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 theyve 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 its important to know it. Its 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 wont further explain the question since its very straightforward. Its 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 Ill 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 its 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 its the 2nd one, output as the 2nd largest element. As you can see, the solution doesnt come from nowhere and Id 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, dont worry since well 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, Ill provide few tips here: You dont 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. Dont 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 its an extremely common techniques and can make your code concise.