C++ program to find kth smallest element in binary search tree.














































C++ program to find kth smallest element in binary search tree.



Discription:  This code is used for displaying  the kth smallest element in a binary search tree . 

#include<iostream.h>
#include<process.h>
#include<conio.h>
#include<stdio.h>
////////////////////////////////////////////////////////
struct stack
{ int item;
  stack *next;
}*start,*p;
////////////////////////////////////////////////////////
static int count;
//////////////////////////////////////////////////////
 void inserts(stack *t,int x)
   {  count++;
      if(t->item==NULL)
{ t->item=x;
  t->next=NULL;
  return;
 }
       else
 {  t=new stack;
    t->item=x;
    p->next=t;
    t->next=NULL;
    p=t;
    return;
  }
    }
////////////////////////////////////////////////////////
void displays(stack *temp)
{  stack *t;
   int a;
   t=temp;
   cout<<"\n Enter the value of k for displaying";     cout<<"kth smallest element from the tree ";
   cin>>a;
   if(a>count)
   {cout<<"\n Entry exceeds the total number";         cout<<"of elements ";
     return;
   }
  for(int i=0;i<count;i++)
   {     if(a==i+1)
    { cout<<"\n "<<(t)->item;
    }
       t=t->next;
    }

}
//////////////////////////////////////////////////////////
struct node
{ int info;
  node *left;
  node *right;
}*root;
/////////////////////////////////////////////////////////
class BST
{ public: void insert(node *,node *);
  void display(node *,int);
  void inorder(node *);
  BST()
  { root = NULL;
  }
};
//////////////////////////////////////////////////////////
void BST::insert(node *tree,node *newnode)
{  if(root==NULL)
     { root=new node;
       root->info = newnode->info;
       root->left=NULL;
       root->right=NULL;
       cout<<"\n Root node is added";
       return;
     }
     if(tree->info==newnode->info)
     { cout<<"\n Element already in the tree ";
       return;
     }
     if(tree->info>newnode->info)
      { if(tree->left!=NULL)
  { insert(tree->left,newnode);

    }
  else
  { tree->left=newnode;
    (tree->left)->left=NULL;
    (tree->left)->right=NULL;
    cout<<"\n Node added to left ";
    return;
  }
      }
      else
       { if(tree->right!=NULL)
  { insert(tree->right,newnode);
  }
  else
  { tree->right=newnode;
    (tree->right)->left=NULL;
    (tree->right)->right=NULL;
    cout<<"\n Node added to left ";
    return;
  }
      }

}
/////////////////////////////////////////////////////////
void BST::display(node *ptr,int level)
{  int i;
    if(ptr!=NULL)
     { display(ptr->right,level+1);
       cout<<"\n";
       if(ptr==root)
   cout<<"ROOT->: ";
else
  { for(i=0;i<level;i++)
     cout<<"     ";
  }
  cout<<ptr->info;
  display(ptr->left,level+1);

     }
}
//////////////////////////////////////////////////////////
void BST::inorder(node *ptr)
 {
      if(ptr!=NULL)
      {
 {
     inorder(ptr->left);
     inserts(p,ptr->info);
     inorder(ptr->right);
 }

      }
 }
 ////////////////////////////////////////////////////////
void main()
{ clrscr();
  int choice,num;
  BST bst;
  node *temp;
  while(1)
  {             cout<<"\n******************************";     cout<<"*********";
 cout<<"\n OPERATIONS ON BINARY SEARCH"; cout<<"TREE ";
    cout<<"\n ************************";             cout<<"******************";
    cout<<"\n 1. Insert ";
    cout<<"\n 2. Display ";
    cout<<"\n 3. Display kth smallest number ";
    cout<<"\n 4. Quit ";
    cout<<"/n/t/t   =>";
    cin>>choice;
    switch(choice)
    { case 1: temp=new node;
      cout<<"\n Enter the number to be";                        cout<<"inserted ";
      cin>>temp->info;
      bst.insert(root,temp);
      continue;
     case 2: cout<<"\n Display BST ";
          bst.display(root,1);
          cout<<"\n";
          if(root==NULL
        { 
       cout<<"\n Tree is empty. NO ELEMENTS !!!!";
    }
     continue;
     case 3:  bst.inorder(root);
     if(root!=NULL)
 displays(start);
     else
cout<<"\n Tree is empty";
     continue;
     case 4:exit(1);
     default: cout<<"\n WRONG CHOICE ";
    }
  }
  getch();
}


Output:


 
 This is the initial output that appears to the screen . The user has to choose one option to be executed. 


 
When the user choose option 1 he has to enter the elements of the binary search tree.
As input elements numerical values (6,8,4,7,5 and 2) are given.
 
 
 

 

 
 

 
 
 
 
 
When the user choose the 2nd option, the binary search tree corresponding to the input elements will be displayed on the screen.



Now the user chose option 3 . He is then asked to enter the value of k so that the kth , smallest element can be displayed.


The input value of k given by the user is 4 . Therefore after 2,4 and 5 the 4th smallest element of the tree is 6.
On choosing option 4 , the user can quit the program .



More Articles of Priyanshi Pal:

Name Views Likes
C++ program to find kth smallest element in binary search tree. 132 1

Comments