Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

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

Posted By: Easy Tutor     Category: C++ Programming     Views: 7281

A C++ Program to show find the maximum depth of a Binary Search Tree.

Code for Program to show find the maximum depth of a Binary Search Tree in C++ Programming

 # 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;
    }
  
Share: 



Easy Tutor
Easy Tutor author of Program to show find the maximum depth of a Binary Search Tree is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 

Other Interesting Articles in C++ Programming:


 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!