Thursday, July 2, 2015

Kth min in BSTree

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

Solution: Use inorder traversal.

Implementation:

//Public interface
int BSTree::kthMin(int k)
{
if(!root || k <= 0)
return -1;
return kthMin(root, k);
}

//Actual Implementation
int BSTree::kthMin(BSTree::Node *node, int& k)
{
static int result = -1;
if(node)
{
kthMin(node->left, k);
if(--k == 0)
result = node->data;
if(k > 0)
return kthMin(node->right, k);
}
else if(k > 0)
result = -1;
return result;
}

Complexity: O(n)

No comments:

Post a Comment