Puzzle 5: Find the 5th largest element in Balanced tree

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.