Puzzle 5: You are given with a balanced tree. Find the 5th largest element in optimal way.
Solution:
Here we will use modified In-Order travesal.
In normal in-order traversal we visit the Left -> Root -> Right and it will produce the sorted list.
So, in order to get the descending list we can reverese the In-Order traversal i.e. visit the Right -> Root- > Left.
Now keep a counter, which counts number of root visited, as soon as counter reachs 5 we will be on the node which is 5th largest.
Here is the example for the same.
Explanation: Here the visited flow will be Right -> Root- > Left.
So 50 will be the answer.
