Showing posts with label Kth smallest element in Binary search tree. Show all posts
Showing posts with label Kth smallest element in Binary search tree. Show all posts

Monday, October 12, 2015

Find Kth smallest element in Binary search tree

/*
TXT file
20 8 22 4 12 10 14 -1
input.txt
*/


#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;//,height;
node * left;
node *right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return -1;
else{
if(t->left==NULL&&t->right==NULL)
return 0;
else
{
int a=height(t->left);
int b=height(t->right);
if(a>b)
return a+1;
else
return b+1;
}
}
}
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}

void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a<t->data)
{
create(t->left,a);
}
else {
create(t->right,a);
}
}
void K_small(node *t,int a,int &c)
{
if(t==NULL||c>=a)
return;
K_small(t->left,a,c);
c++;
if(a==c){

cout<<t->data<<" is kth K_small element\n";
return ;
}
K_small(t->right,a,c);
}

int main()
{
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a;
fin>>a;
while(a!=-1)
{
create(t,a);
fin>>a;
}

fin.close();
print(t);
cout<<endl;
int c=0;
K_small(t,3,c);
return 0;
}

Contributors

Translate