Note this is an Algorithm class You are given a binary searc

Note: this is an Algorithm class

You are given a binary search tree. How to find its third largest element?

Solution

We run the inverse of inorder traversal (RCL) but instead of priting all the elements we maintain a track of position of each element in the sequence of nodes visited. As this is a BST the nodes will be visited in an descending order and when we reach the third element we stop the loop and print the element. This takes approximately O(logn) time.