Thursday, February 2, 2012

kth largest /smallest element in a BST

How to find kth smallest element in BST. you cannot use static/global variable and you cannot pass value of k to any function ?

http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/

Using static variable:
Traverse the tree in descending order and keep a count of number of nodes visited. 
When this count is equal to 'k', print the element. 
 
void printk(struct node* root, int k)
{
    if(root == NULL)
        return;
    static int index = 0;
    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }
    printk(root->left, k);
}

Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

struct node* insert(struct node* node, int data)
{

if (node == NULL)
return(newNode(data));
else
{
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);


return node;
}
}

int kthMax(struct node* t, int *k) {

if(t == NULL)
return INT_MIN;

int x = kthMax(t->right, k);

if(x != INT_MIN) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMax(t->left, k);
}

int kthMin(struct node* t, int *k) {

if(t == NULL)
return INT_MAX;

int x = kthMin(t->left, k);

if(x != INT_MAX) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMin(t->right, k);
}

int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

int n=2,m=3;
printf("Given kth Min in BST is %d \t kth Max is=%d", kthMin(root,&n),kthMax(root,&m));
getchar();
return 0;
}

No comments:

Post a Comment