**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.

## No comments:

## Post a Comment