# include <iostream.h>
 # include    <conio.h>

 /**************************************************************************///-------------------------------  Tree  ---------------------------------///**************************************************************************/class Tree
    {
       private:
      int data;

      Tree *Left;
      Tree *Right;

       public:
      Tree *Root_node;
      Tree *Location;
      Tree *Parent;

      Tree( ) { Root_node=NULL; }

      Tree* insert_element(Tree*,int);

      // These two functions are used to find the max tree depthint get_tree_depth(Tree*);

      void find_tree_depth(Tree*,int,int&);


      void search_element(int);
      void delete_element(int);
      void delete_element_with_0_or_1_child( );
      void delete_element_with_2_child( );
      void print_tree_in_post_order(Tree*);
      void print_tree_in_pre_order(Tree*);
      void print_tree_in_in_order(Tree*);
      void show_working( );
    };


 /*************************************************************************///--------------------------  insert_element( )  ------------------------///*************************************************************************/

 Tree* Tree::insert_element(Tree *root,int data)
    {
       if(root==NULL)
      {
         Tree *Temp;

         Temp=new Tree;

         Temp->data=data;
         root=Temp;
         root->Left=NULL;
         root->Right=NULL;

         cout<<"\n\n\t *** "<<data<<" is inserted into the Tree."<<endl;
         cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

         getch( );
      }

       else
      {
         Parent=root;

         if(data>root->data)
        {
           if(root->Right==NULL)
              root->Right=insert_element(root->Right,data);

           else
              insert_element(root->Right,data);
        }

         else
        {
           if(root->Left==NULL)
              root->Left=insert_element(root->Left,data);

           else
              insert_element(root->Left,data);
        }
      }

       return root;
    }

 /*************************************************************************///---------------------  print_tree_in_pre_order( )  --------------------///*************************************************************************/void Tree::print_tree_in_pre_order(Tree *root)
    {
       if(root==NULL)
      {  }

       else
      {
         cout<<"\t "<<root->data<<endl;

         if(root->Left!=NULL)
        print_tree_in_pre_order(root->Left);

         if(root->Right!=NULL)
        print_tree_in_pre_order(root->Right);
      }
    }

 /*************************************************************************///---------------------  print_tree_in_post_order( )  -------------------///*************************************************************************/void Tree::print_tree_in_post_order(Tree *root)
    {
       if(root==NULL)
      {  }

       else
      {
         if(root->Left!=NULL)
        print_tree_in_post_order(root->Left);

         if(root->Right!=NULL)
        print_tree_in_post_order(root->Right);

         cout<<"\t "<<root->data<<endl;
      }
    }

 /*************************************************************************///-----------------------  print_tree_in_in_order( )  -------------------///*************************************************************************/void Tree::print_tree_in_in_order(Tree *root)
    {
       if(root==NULL)
      {  }

       else
      {
         if(root->Left!=NULL)
        print_tree_in_in_order(root->Left);

         cout<<"\t "<<root->data<<endl;

         if(root->Right!=NULL)
        print_tree_in_in_order(root->Right);
      }
    }

 /*************************************************************************///-------------------------  search_element( )  -------------------------///*************************************************************************/void Tree::search_element(int Search_key)
    {
       int depth=1;
       int left_right=0;

       Tree *Pointer=NULL;
       Tree *Save=NULL;

       Location=NULL;
       Parent=NULL;

       if(Root_node==NULL)
      {
         Location=NULL;
         Parent=NULL;
      }

       elseif(Search_key==Root_node->data)
      {
         Location=Root_node;
         Parent=NULL;

         depth=1;
      }

       else
      {
         if(Search_key<Root_node->data)
        {
           Pointer=Root_node->Left;

           left_right=1;
        }

         else
        {
           Pointer=Root_node->Right;

           left_right=2;
        }

         Save=Root_node;

         while(Pointer!=NULL)
        {
           depth+=1;

           if(Search_key==Pointer->data)
              {
             Location=Pointer;
             Parent=Save;

             break;
              }

           elseif(Search_key<Pointer->data)
              {
             Save=Pointer;
             Pointer=Pointer->Left;
              }

           elseif(Search_key>Pointer->data)
              {
             Save=Pointer;
             Pointer=Pointer->Right;
              }
        }
      }

       if(Location==NULL)
      {
         Parent=NULL;

         cout<<"\n\n\n\n\n\t *** "<<Search_key<<" is not found in the Tree. "<<endl;
      }

       elseif(Location!=NULL)
      {
         if(left_right==0)
        cout<<"\n\n\n\t ***  "<<Search_key<<" is the Root Node."<<endl;

         elseif(left_right==1)
        cout<<"\n\n\n\t ***  "<<Search_key<<" lies at the Left side of the Root Node ";

         elseif(left_right==2)
        cout<<"\n\n\n\t ***  "<<Search_key<<" lies at the Right side of the Root Node ";

         if(left_right)
        cout<<"and at the depth level "<<depth<<endl;
      }

       cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

       getch( );
    }

 /*************************************************************************///---------------  delete_element_with_0_or_1_child( )  -----------------///*************************************************************************/void Tree::delete_element_with_0_or_1_child( )
    {
       Tree *Child;

       if(Location->Left==NULL && Location->Right==NULL)
      Child=NULL;

       elseif(Location->Left!=NULL)
      Child=Location->Left;

       else
      Child=Location->Right;

       if(Parent!=NULL)
      {
         if(Location==Parent->Left)
        Parent->Left=Child;

         else
        Parent->Right=Child;
      }

       else
      Root_node=Child;
    }

 /*************************************************************************///-------------------  delete_element_with_2_child( )  ------------------///*************************************************************************/void Tree::delete_element_with_2_child( )
    {
       Tree *Pointer=Location->Right;
       Tree *Save=Location;

       Tree *Sucessor;
       Tree *Parent_sucessor;

       while(Pointer->Left!=NULL)
      {
         Save=Pointer;
         Pointer=Pointer->Left;
      }

       Sucessor=Pointer;
       Parent_sucessor=Save;

       Tree *temp_loc=Location;
       Tree *temp_par=Parent;

       Location=Sucessor;
       Parent=Parent_sucessor;

       delete_element_with_0_or_1_child( );

       Location=temp_loc;
       Parent=temp_par;

       if(Parent!=NULL)
      {
         if(Location==Parent->Left)
        Parent->Left=Sucessor;

         else
        Parent->Right=Sucessor;
      }

       else
      Root_node=Sucessor;

       Sucessor->Left=Location->Left;
       Sucessor->Right=Location->Right;
    }

 /*************************************************************************///------------------------  delete_element( )  --------------------------///*************************************************************************/void Tree::delete_element(int delete_key)
    {
       search_element(delete_key);

       if(Root_node==NULL)
      cout<<"\n\n\n\t ***  Error : Tree is empty. \n"<<endl;

       elseif(Location==NULL)
      cout<<"\n\n\n\t ***  "<<delete_key<<"  does not exists in the tree \n"<<endl;

       else
      {
         if(Location->Right!=NULL && Location->Left!=NULL)
        delete_element_with_2_child( );

         else
        delete_element_with_0_or_1_child( );

         cout<<"\n\n\n\t *** "<<delete_key<<" is deleted from the Tree."<<endl;
         cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

         getch( );
      }
    }

 /*************************************************************************///------------------------  get_tree_depth( )  --------------------------///*************************************************************************/int Tree::get_tree_depth(Tree *root)
    {
       int depth=0;
       int temp=-1;

       find_tree_depth(root,temp,depth);

       return depth;
    }

 /*************************************************************************///------------------------  get_tree_depth( )  --------------------------///*************************************************************************/void Tree::find_tree_depth(Tree *root,int temp,int& depth)
    {
       if(root==NULL)
      {

      }

       else
      {
         temp++;

         if(temp>depth)
        depth=temp;

         if(root->Left!=NULL)
        find_tree_depth(root->Left,temp,depth);

         if(root->Right!=NULL)
        find_tree_depth(root->Right,temp,depth);
      }
    }

 /*************************************************************************///--------------------------  show_working( )  --------------------------///*************************************************************************/void Tree::show_working( )
    {
       char Key=NULL;

       do
      {
         clrscr( );

         gotoxy(5,5);
         cout<<"********  Implementation of Linked List as a Binary Search Tree  ********"<<endl;

         gotoxy(10,8);
         cout<<"Select one of the listed operation :"<<endl;

         gotoxy(15,10);
         cout<<"- Press \'I\' to Insert a value"<<endl;

         gotoxy(15,12);
         cout<<"- Press \'D\' to Delete a value"<<endl;

         gotoxy(15,14);
         cout<<"- Press \'P\' to Print the values in In-Order"<<endl;

         gotoxy(15,16);
         cout<<"- Press \'Q\' to Print the values in Pre-Order"<<endl;

         gotoxy(15,18);
         cout<<"- Press \'R\' to Print the values in Post-Order"<<endl;

         gotoxy(15,20);
         cout<<"- Press \'T\' to Print the max. Tree Depth"<<endl;

         gotoxy(15,22);
         cout<<"- Press \'E\' to Exit"<<endl;

         Input:

         gotoxy(10,26);
         cout<<"                      ";

         gotoxy(10,26);
         cout<<"Enter your Choice : ";

         Key=getche( );

         if(int(Key)==27 || Key=='e' || Key=='E')
        break;

         elseif(Key=='i' || Key=='I')
        {
           int item;

           cout<<"\n\n\n\n\n\t Enter the value to insert into Tree : ";
           cin>>item;

           if(Root_node==NULL)
              Root_node=insert_element(Root_node,item);

           else
              insert_element(Root_node,item);
        }

         elseif(Key=='d' || Key=='D')
        {
           int item;

           cout<<"\n\n\n\n\n\t Enter the value to delete from Tree : ";
           cin>>item;

           delete_element(item);
        }

         elseif(Key=='s' || Key=='S')
        {
           int item;

           cout<<"\n\n\n\n\n\t Enter the value to search from Tree : ";
           cin>>item;

           search_element(item);
        }

         elseif(Key=='p' || Key=='P')
        {
           if(Root_node!=NULL)
              cout<<"\n\n\n\n\n\t Values of Tree in In-Order are : \n"<<endl;

           else
              cout<<"\n\n\n\n\n\t *** Nothing to show. "<<endl;

           print_tree_in_in_order(Root_node);

           cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

           getch( );
        }

         elseif(Key=='q' || Key=='Q')
        {
           if(Root_node!=NULL)
              cout<<"\n\n\n\n\n\t Values of Tree in Pre-Order are : \n"<<endl;

           else
              cout<<"\n\n\n\n\n\t *** Nothing to show. "<<endl;

           print_tree_in_pre_order(Root_node);

           cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

           getch( );
        }

         elseif(Key=='r' || Key=='R')
        {
           if(Root_node!=NULL)
              cout<<"\n\n\n\n\n\t Values of Tree in Post-Order are : \n"<<endl;

           else
              cout<<"\n\n\n\n\n\t *** Nothing to show. "<<endl;

           print_tree_in_post_order(Root_node);

           cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

           getch( );
        }

         elseif(Key=='t' || Key=='T')
        {
           if(Root_node!=NULL)
              cout<<"\n\n\n\n\n\t Tree Depth = "<<get_tree_depth(Root_node)<<endl;

           else
              cout<<"\n\n\n\n\n\t *** Nothing to show. "<<endl;

           cout<<"\n\n\n\t\t Pres any key to return to Menu. ";

           getch( );
        }

         elsegoto Input;
      }
       while(1);
    }

 /*************************************************************************///----------------------------  main( )  --------------------------------///*************************************************************************/int main( )
    {
       Tree tree_obj;

       tree_obj.show_working( );

       return 0;
    }