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/
#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;
}
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