Nth largest element in a binary search tree

Question

How to find the Nth largest node in a BST?

Do I keep a count variable while doing In Order Traversal of a BST? Return the element when the count = N???

Answer 1

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);