**Problem:**Write a method which returns the kth maximum element in a given Binary Search Tree.

**Solution:**Use reverse inorder traversal.

**Implementation:**

//Public interface

int BSTree::kthMax(int k)

{

if(!root || k <= 0)

return -1;

return kthMax(root, k);

}

//Actual implementation

int BSTree::kthMax(BSTree::Node *node, int& k)

{

static int result = -1;

if(node)

{

kthMax(node->right, k);

if(--k == 0)

result = node->data;

if(k > 0)

return kthMax(node->left, k);

}

else if(k > 0)

result = -1;

return result;

}

**Complexity:**O(n)

## No comments:

## Post a Comment