Nth largest element in a binary search tree

The idea is very simple: traverse the tree in decreasing order of the values of each node. When you reach the Nth node, print that node value. Here is the recursive code.

void printNthNode(Node* root, int N)
{
   if(root == NULL)
       return;

   static int index = 0; //These will initialize to zero only once as its static

   //For every Node go to the right of that node first.
   printNthNode(root->right, N);


   //Right has returned and now current node will be greatest
   if(++index == N)
   {
    printf("%d\n", root->data);
    return;
   }

   //And at last go to the left
   printNthNode(root->left, N);
}

Edit - As per the comments below, looks like this is one-time call function due to the static local variable. This can be solved by passing wrapper object for index as follows:

    class WrapIndex {
         public: int index;
    };

and method signature would change to

void printNthNode(Node* root, int N, WrapIndex wrapInd)

Now, we don't need a local static variable; instead use index of the wrapper object. The call would look like

WrapIndex wrapInd = new WrapIndex();
wrapInd.index=0;
printNthNode(root,7,wrapInd);

wrapInd.index=0;
printNthNode(root,2,wrapInd);

Hint: use inorder traversal of the tree. It can print out the items in sorted order, so you can sure find the Nth largest item. Keep a counter as you "walk", incrementing each time you "visit" a node.

Edit: while IVlad's answer is indeed faster, it requires you to keep extra information in the nodes. This answer doesn't but it's O(n). Just pointing out that this is a tradeoff you have to be aware of.

See my answer here. You can do this in O(log n) on average where n = number of nodes. Worst case is still O(n) IF the tree isn't balanced (always O(log n) if it is balanced however). In order traversal is always O(n) however.