Just No more free questions left!
Upgrade NowWrite a function to find the 2nd largest element in a binary search tree.
Here's a sample binary tree node class:
Our first thought might be to do an in-order traversal of the BST and return the second-to-last item. This means looking at every node in the BST. That would take time and space, where h is the max height of the tree (which is lgn if the tree is balanced, but could be as much as n if not).
We can do better than time and space.
We can do this in one walk from top to bottom of our BST. This means time (again, that's if the tree is balanced, otherwise).
A clean recursive implementation will take space in the call stack, but we can bring our algorithm down to space overall.
Let's start by solving a simplified version of the problem and see if we can adapt our approach from there. How would we find the largest element in a BST?
A reasonable guess is to say the largest element is simply the "rightmost" element.
So maybe we can start from the root and just step down right child pointers until we can't anymore (until the right child is null). At that point the current node is the largest in the whole tree.
Is this sufficient? We can prove it is by contradiction:
If the largest element were not the "rightmost," then the largest element would either:
But each of these leads to a contradiction:
So the "rightmost" element must be the largest.
How would we formalize getting the "rightmost" element in code?
We can use a simple recursive approach. At each step:
Okay, so we can find the largest element. How can we adapt this approach to find the second largest element?
Our first thought might be, "it's simply the parent of the largest element!" That seems obviously true when we imagine a nicely balanced tree like this one:
But what if the largest element itself has a left subtree?
Here the parent of our largest is 8, but the second largest is 11.
Drat, okay so the second largest isn't necessarily the parent of the largest...back to the drawing board...
Wait. No. The second largest is the parent of the largest if the largest does not have a left subtree. If we can handle the case where the largest does have a left subtree, we can handle all cases, and we have a solution.
So let's try sticking with this. How do we find the second largest when the largest has a left subtree?
It's the largest item in that left subtree! Whoa, we freaking just wrote a function for finding the largest element in a tree. We could use that here!
How would we code this up?
Okay awesome. This'll work. It'll take h time (where h is the height of the tree) and space.
But that h space in the call stack is avoidable. How can we get this down to constant space?
We start with a function for getting the largest value. The largest value is simply the "rightmost" one, so we can get it in one walk down the tree by traversing rightward until we don't have a right child anymore:
With this in mind, we can also find the second largest in one walk down the tree. At each step, we have a few cases:
We're doing one walk down our BST, which means time, where h is the height of the tree (again, that's if the tree is balanced, otherwise). space.
Here we used a "simplify, solve, and adapt" strategy.
The question asks for a function to find the second largest element in a BST, so we started off by simplifying the problem: we thought about how to find the first largest element.
Once we had a strategy for that, we adapted that strategy to work for finding the second largest element.
It may seem counter-intuitive to start off by solving the wrong question. But starting off with a simpler version of the problem is often much faster, because it's easier to wrap our heads around right away.
One more note about this one:
Breaking things down into cases is another strategy that really helped us here.
Notice how simple finding the second largest node got when we divided it into two cases:
Whenever a problem is starting to feel complicated, try breaking it down into cases.
It can be really helpful to actually draw out sample inputs for those cases. This'll keep your thinking organized and also help get your interviewer on the same page.