CareerCup

Use order stastistics , at every node left count is given

::Reverse In-order traversal::
int Klargest(struct node* root,int k)
{
int static count=0;
Klargest(root->right ,k);
if(++count==k)cout<<root->value;
Klargest(root->left,k);
}

If deletion is allowed, we can do the following

findKthMax(Node t){

maxCount = 1;
Node maxNode;
while(maxCount <= k ){

maxNode = max(tree);
deleteNode(tree,maxNode)
maxCount++;

}

return maxNode;

}

max(Node tree) and deleteNode() have O(logN) complexity, and the algo has O(klogN) = O(logN) complexity

}

I think this can be done in O( H ) , H = height of BST
But that would require every node of the tree to have following information:
1)number of nodes smaller that that node

Assuming we have this info. then we start at root and
1)if k > number of nodes smaller that this node ,we move to its right child
2)else if k < number of nodes smaller that this node ,we move to its left child
3) else if k == number of nodes smaller that this node , this is the node we are looking for

but again to get the required info, we have to first traverse the tree in inorder fashion , which is of order O(n).
so without the above mentioned info , i think , we cant do it in O(h).