Program to show find the maximum depth of a Binary Search Tree

 # 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 depth
      int 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;
      }

       else if(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;
              }

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

           else if(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;
      }

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

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

         else if(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;

       else if(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;

       else if(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;

         else if(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);
        }

         else if(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);
        }

         else if(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);
        }

         else if(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( );
        }

         else if(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( );
        }

         else if(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( );
        }

         else if(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( );
        }

         else
        goto Input;
      }
       while(1);
    }


 //----------------------------  main( )  --------------------------------//


 int main( )
    {
       Tree tree_obj;

       tree_obj.show_working( );

       return 0;
    }