Binary Search Tree Program In C++

//Program using Linked List

#include <iostream>
#include<cstdlib>
using namespace std;
struct bst_node
{
  	int bst_data;
  	struct bst_node *left_subtree;
  	struct bst_node *right_subtree;
} *root_of_tree;

class Binary_Search_Tree
{
public:
  		void bst_find (int, bst_node **, bst_node **);
  		void bst_insert (bst_node *, bst_node *);
  		void bst_del (int);
  		void bst_case_a (bst_node *, bst_node *);
  		void bst_case_b (bst_node *, bst_node *);
  		void bst_case_c (bst_node *, bst_node *);
  		void bst_preorder (bst_node *);
  		void bst_inorder (bst_node *);
  		void bst_postorder (bst_node *);
  		void bst_display (bst_node *, int);
  		Binary_Search_Tree ()
  		{
    			root_of_tree = NULL;
  		}
};

int main ()
{
  	char chh;
  	int choiicee, nuum;
  	Binary_Search_Tree bst;
  	bst_node *tempo;
  	while (1)
   	{
      		cout << "-------------" << endl;
      		cout << "Following are the Operations on BST" << endl;
      		cout << "-------------" << endl;
      		cout << "1.Press 1 to Insert Element" << endl;
      		cout << "2.Press 2 to Delete Element" << endl;
      		cout << "3.Press 3 for Inorder Traversal" << endl;
      		cout << "4.Press 4 for Preorder Traversal" << endl;
      		cout << "5.Press 5 for Postorder Traversal" << endl;
      		cout << "6.Press 6 to Display" << endl;
      		cout << "7.Press 7 to Quit" << endl;
      		cout << "User please enter your choice : ";
      		cin >> choiicee;
                        switch (choiicee)
                       {
	                case 1:
	  	            cout << "Enter 'Y' to insert element or 'N' to exit";
	  	            cin >> chh;
	  	            while (chh == 'Y' || chh == 'y')
	  	            {  
	      		     tempo = new bst_node;
	      		     cout << "Insert element: ";
	      		     cin >> tempo->bst_data;
	      	 	     bst.bst_insert (root_of_tree, tempo);
	      		         //break;
	      		     cout << "Press 'Y' to enter next element";
	      		     cin >> chh;
	  	             }
		                  break;
	                 
                        case 2:
		         if (root_of_tree == NULL)
		        {
	      	             cout << "Binary search Tree is empty,nothing to delete" << endl;
	      	             continue;
		         }
		         cout << "Enter the node number to be deleted";
		         cin >> nuum;
		         bst.bst_del (nuum);
		         break;
	            case 3:
		   cout << "Following is the Inorder Traversal of Binary Search Tree:"   << endl;
		        bst.bst_inorder (root_of_tree);
		        cout << endl;
		        break;
	            case 4:
		        cout << "Following is the Preorder Traversal of BST:" << endl;
		        bst.bst_preorder (root_of_tree);
		        cout << endl;
		        break;
	           case 5:
		        cout << "Following is the Postorder Traversal of BST:" << endl;
		        bst.bst_postorder (root_of_tree);
		        cout << endl;
		        break;
	           case 6:
	  	        cout << "Following is the Dispaly of BST :" << endl;
	  	        bst.bst_display (root_of_tree, 1);
	  	        cout << endl;
	   	        break;
	          case 7:
	  	        exit (1);
	          default:
	  	        cout << "You have entered Wrong choice" << endl;
	}
    }
}

void Binary_Search_Tree::bst_find (int iteem, bst_node ** parr, bst_node ** looc)
{
        bst_node *ptrr, *ptrrsave;
        if (root_of_tree == NULL)
       {
            *looc = NULL;
            *parr = NULL;
             return;
        }
       if (iteem == root_of_tree->bst_data)
      {
           *looc = root_of_tree;
           *parr = NULL;
           return;
       }
       if (iteem < root_of_tree->bst_data)
      {
           ptrr = root_of_tree->left_subtree;
      }
      else
     {
          ptrr = root_of_tree->right_subtree;
      }
          ptrrsave = root_of_tree;
          while (ptrr != NULL)
         {
               if (iteem == ptrr->bst_data)
	  {
	     *looc = ptrr;
	     *parr = ptrrsave;
	      return;
	  }
              ptrrsave = ptrr;
              if (iteem < ptrr->bst_data)
	  {
	     ptrr = ptrr->left_subtree;
	  }
      else
	  {
	     ptrr = ptrr->right_subtree;
	  }
      *looc = NULL;
      *parr = ptrrsave;
    }
}

void Binary_Search_Tree::bst_insert (bst_node * bst_tree, bst_node * bst_newnode)
{
    if(root_of_tree == NULL)
    {
      root_of_tree = new bst_node;
      root_of_tree->bst_data = bst_newnode->bst_data;
      root_of_tree->left_subtree = NULL;
      root_of_tree->right_subtree = NULL;
      cout << "Root Node is Added to Binary Search Tree" << endl;
      return;
    }
    if (bst_tree->bst_data == bst_newnode->bst_data)
    {
      cout << "Element already in the Binary Search tree" << endl;
      return;
    }
    if (bst_tree->bst_data > bst_newnode->bst_data)
    {
       if (bst_tree->left_subtree != NULL)
	   {
	      bst_insert (bst_tree->left_subtree, bst_newnode);
	   }
       else
	   {
	      bst_tree->left_subtree = bst_newnode;
	      (bst_tree->left_subtree)->left_subtree = NULL;
	      (bst_tree->left_subtree)->right_subtree = NULL;
	      cout << "Node Added to left of Binary Search Tree" << endl;
	      return;
	   }
    }
    else
    {
      if (bst_tree->right_subtree != NULL)
	  {
	     bst_insert (bst_tree->right_subtree, bst_newnode);
	  }
      else
	  {
	    bst_tree->right_subtree = bst_newnode;
	    (bst_tree->right_subtree)->left_subtree = NULL;
	    (bst_tree->right_subtree)->right_subtree = NULL;
	    cout << "Node Added To Right of Binary Search Tree" << endl;
	    return;
	  }
    }
}

void Binary_Search_Tree::bst_del (int iteem)
{
  bst_node *bst_parent, *loocation;
  if (root_of_tree == NULL)
    {
      cout << "Binary Search Tree empty" << endl;
      return;
    }

  bst_find (iteem, &bst_parent, &loocation);

  if (loocation == NULL)
    {
      cout << "Item not present in the Binary Search tree" << endl;
      return;
    }

  if (loocation->left_subtree == NULL && loocation->right_subtree == NULL)
    {
      bst_case_a (bst_parent, loocation);
    }
  if (loocation->left_subtree != NULL && loocation->right_subtree != NULL)
    {
      bst_case_b (bst_parent, loocation);
    }
  if (loocation->left_subtree != NULL && loocation->right_subtree != NULL)
    {
      bst_case_c (bst_parent, loocation);
    }
  free (loocation);
}

void Binary_Search_Tree::bst_case_a (bst_node * parr, bst_node * looc)
{
  if (parr == NULL)
  {
      root_of_tree = NULL;
  }
  else
  {
      if (looc == parr->left_subtree)
	  {
	     parr->left_subtree = NULL;
	  }
      else
	  {
	     parr->right_subtree = NULL;
	  }
  }
}



void Binary_Search_Tree::bst_case_b (bst_node * parr, bst_node * looc)
{
      bst_node *chilld;
      if (looc->left_subtree != NULL)
     {
          chilld = looc->left_subtree;
      }
      else
     {
          chilld = looc->right_subtree;
     }
     if (parr == NULL)
     {
         root_of_tree = chilld;
     }
     else
     {
         if (looc == parr->left_subtree)
	  {
	    parr->left_subtree = chilld;
	  }
      else
	  {
	    parr->right_subtree = chilld;
	  }
      }
}

void Binary_Search_Tree::bst_case_c (bst_node * parr, bst_node * looc)
{
      bst_node *ptrr, *ptrrsave, *suc, *parsuc;
      ptrrsave = looc;
     ptrr = looc->right_subtree;
     while (ptrr->left_subtree != NULL)
     {
         ptrrsave = ptrr;
         ptrr = ptrr->left_subtree;
    }
    suc = ptrr;
    parsuc = ptrrsave;
  if (suc->left_subtree == NULL && suc->right_subtree == NULL)
    {
      bst_case_a (parsuc, suc);
    }
  else
    {
      bst_case_b (parsuc, suc);
    }
  if (parr == NULL)
    {
      root_of_tree = suc;
    }
  else
    {
      if (looc == parr->left_subtree)
	{
	  parr->left_subtree = suc;
	}
      else
	{
	  parr->right_subtree = suc;
	}
      suc->left_subtree = looc->left_subtree;
      suc->right_subtree = looc->right_subtree;
    }
}

void Binary_Search_Tree::bst_preorder (bst_node * ptrr)
{
    if (root_of_tree == NULL)
    {
      cout << "Binary Search Tree is empty" << endl;
      return;
    }
    if (ptrr != NULL)
    {
      cout << "Binary Search Tree is empty" << endl;
      return;
    }
    if (ptrr != NULL)
    {
      cout << ptrr->bst_data << " ";
      bst_preorder (ptrr->left_subtree);
      bst_preorder (ptrr->right_subtree);
    }
}

void Binary_Search_Tree::bst_inorder (bst_node * ptrr)
{
     if (root_of_tree == NULL)
     {
         cout << "Binary Search Tree is empty" << endl;
         return;
      }
     if (ptrr != NULL)
     {
         bst_inorder (ptrr->left_subtree);
         cout << ptrr->bst_data << " ";
         bst_inorder (ptrr->right_subtree);
      }
}
void Binary_Search_Tree::bst_postorder (bst_node * ptrr)
{
      if (root_of_tree == NULL)
     {
        cout << "Binary Search Tree is empty" << endl;
        return;
      }
      if (ptrr != NULL)
     {
         bst_postorder (ptrr->left_subtree);
         bst_postorder (ptrr->right_subtree);
         cout << ptrr->bst_data << " ";
    }
}

void Binary_Search_Tree::bst_display (bst_node * ptrr, int bst_level)
{
     int i;
     if (ptrr != NULL)
     {
         bst_display (ptrr->right_subtree, bst_level + 1);
         cout << endl;
         if (ptrr == root_of_tree)
         {
	  cout << "Root ->: ";
          }
      else
         {
	  for (i = 0; i < bst_level; i++)
	    {
	      cout << "     ";
	    }
           }
           cout << ptrr->bst_data;
           bst_display (ptrr->left_subtree, bst_level + 1);
    }
}
Output:
-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 1

Enter 'Y' to insert element or 'N' to exity

Insert element: 8

Root Node is Added to Binary Search Tree

Press 'Y' to enter next elementy

Insert element: 2

Node Added to left of Binary Search Tree

Press 'Y' to enter next elementy

Insert element: 5

Node Added To Right of Binary Search Tree

Press 'Y' to enter next elementy

Insert element: 9

Node Added To Right of Binary Search Tree

Press 'Y' to enter next element10

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : You have entered Wrong choice

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 6

Following is the Display of BST :



          9

Root ->: 8

               5

          2

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 3
Following is the Inorder Traversal of Binary Search Tree:

2 5 8 9 

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 4

Following is the Preoder Traversal of BST:

Binary Serach Tree is empty



-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 5

Following is the Postorder Traversal of BST:

5 2 9 8 

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 6

Following is the Display of BST :



          9

Root ->: 8

               5

          2

-------------

Following are the Operations on BST

-------------

Press 1 to Insert Element

Press 2 to Delete Element

Press 3 for Inorder Traversal

Press 4 for Preorder Traversal

Press 5 for Postorder Traversal

Press 6 to Display

Press 7 to Quit

User please enter your choice : 7
Code Analysis:

Binary Search Tree (BST) is a data structure having following properties:
Left subtree contains all nodes having value less than root node value.
Right subtree contains all nodes having value greater than root node value.
Left subtree and right subtree follow the property of the binary search tree.

Inserting node in Binary Search Tree 
First node that is inserted is called the root node of the tree. Next node to be inserted will be compared with the root - if its value is less, then it will be inserted in the left subtree, and if the value to be inserted is greater than root, then it will be inserted in the right subtree. This operation is performed by following function is the above code:
void bst_insert (bst_node *, bst_node *);
Inorder Traversal of BST
In BST, Inorder traversal projects nodes in left, root and right order. That is, the left subtree is accessed first, than root is accessed and than nodes of right subtree is accessed.
In the above code, this operation is performed by following function:
void bst_inorder (bst_node *);

Postorder Traversal of BST
In BST, Postorder traversal projects nodes in Left, Right and Root order. In postorder traversal the left subtree is accessed first, than the right subtree is accessed and than root of the tree is accessed.
In the above code, this operation is performed by following function:
void bst_postorder (bst_node *);

Preorder Traversal of BST
In BST, Preorder traversal projects nodes in Root, Left, and Right order. In
Preorder traversal nodes processing begins by processing the root node, left subtree is processed and then right subtree is processed.
In the above code, this operation is performed by following function:
void bst_postorder (bst_node *);

To display full Binary Search Tree, above code use the following function:
void bst_display (bst_node *, int);
//Program for Binary Search Tree using Stack data structure

#include <iostream>
#include<cstdlib>
using namespace std;

class binary_node_stk
{
    public:
        int bst_data;
        binary_node_stk *left_subtree;
        binary_node_stk *right_subtree;
};




class bin_src_tree
{
    private:
        binary_node_stk *bst_root;
        void inorder_rec(binary_node_stk *);
        void inorder_non_rec(binary_node_stk *);
        void preorder_rec(binary_node_stk *);
        void preorder_non_rec(binary_node_stk *);
        void postorder_rec(binary_node_stk *);
        void postorder_non_rec(binary_node_stk *);
    public:
            bin_src_tree( )
            {
                bst_root=NULL;
            }
        void insert(int );
        void print_inorder_rec( );
        void print_inorder_non_rec( );
        void print_preorder_rec( );
        void print_preorder_non_rec( );
        void print_postorder_rec( );
        void print_postorder_non_rec( );
};

class s_tack
{
        int bst_top;
        binary_node_stk *stack_op[20];
        public:
            s_tack()
            {
                bst_top=-1;
            }
            void bst_push(binary_node_stk *);
            binary_node_stk* bst_pop();
            int empty()
            {
                if(bst_top==-1)
                return(1);

                return(0);
            }
};

void s_tack::bst_push(binary_node_stk *bst_node)
{
        stack_op[++bst_top]=bst_node;
}

binary_node_stk *s_tack::bst_pop( )
{
        return(stack_op[bst_top--]);
}

class s_tack_int
{
        int bst_top;
        int s_tack_init[20];
            public:
                s_tack_int()
                {
                    bst_top=-1;
                }
        void bst_push(int f_lag);
        int bst_pop( );
        int empty_int( )
        {
            if(bst_top==-1)
            return(1);

            return(0);
        }
};

void s_tack_int::bst_push(int f_lag)
{
        s_tack_init[++bst_top]=f_lag;
}

int s_tack_int::bst_pop( )
{
        return(s_tack_init[bst_top--]);
}

void bin_src_tree::insert(int bst_val)
{
        binary_node_stk *tempo,*bst_prev,*bst_curr;
        tempo=new binary_node_stk;
        tempo->bst_data=bst_val;
        tempo->left_subtree=tempo->right_subtree=NULL;

        if(bst_root==NULL)
        {
            bst_root=tempo;
        }
        else
        {
            bst_curr=bst_root;
            while(bst_curr!=NULL)
            {
                    bst_prev=bst_curr;
                    if(tempo->bst_data<bst_curr->bst_data)
                        bst_curr=bst_curr->left_subtree;
                    else
                        bst_curr=bst_curr->right_subtree;
            }
            if(tempo->bst_data<bst_prev->bst_data)
                bst_prev->left_subtree=tempo;
            else
                bst_prev->right_subtree=tempo;
        }
}

void bin_src_tree::inorder_rec(binary_node_stk *bst_root)
{
        if(bst_root!=NULL)
        {
            inorder_rec(bst_root->left_subtree);
            cout<<bst_root->bst_data<<"	";
            inorder_rec(bst_root->right_subtree);
        }
}

void bin_src_tree::inorder_non_rec(binary_node_stk *bst_root)
{
        s_tack stk;
        binary_node_stk *tempo;
        if(bst_root!=NULL)
        {
            tempo=bst_root;
            do
            {
                while(tempo!=NULL)
                {
                    stk.bst_push(tempo);
                    tempo=tempo->left_subtree;
                }/*end while*/
                if(!stk.empty( ))
                {
                        tempo=stk.bst_pop( );
                        cout<<tempo->bst_data<<"	";
                        tempo=tempo->right_subtree;
                }/*end if*/
                else
                        break;
            }while(1); /*end do while*/
        }
        else
            cout<<"Empty tree";

} 

void bin_src_tree::preorder_rec(binary_node_stk *bst_root)
{
        if(bst_root!=NULL)
        {
           cout<<bst_root->bst_data<<"	";
           preorder_rec(bst_root->left_subtree);
           preorder_rec(bst_root->right_subtree);
        }
}

void bin_src_tree ::preorder_non_rec(binary_node_stk *bst_root)
{
        s_tack stk;
        binary_node_stk *tempo=bst_root;

        stk.bst_push(tempo);

        while(!stk.empty( ))
        {
            tempo=stk.bst_pop( );
            if(tempo!=NULL)
            {
                cout<<tempo->bst_data<<"	";
                stk.bst_push(tempo->right_subtree);
                stk.bst_push(tempo->left_subtree);
            }
        }

}



void bin_src_tree::postorder_rec(binary_node_stk *bst_root)
{
        if(bst_root!=NULL)
        {
            postorder_rec(bst_root->left_subtree);
            postorder_rec(bst_root->right_subtree);
            cout<<bst_root->bst_data<<"	";
        }
}

void bin_src_tree::postorder_non_rec(binary_node_stk *bst_root)
{
         s_tack stk;
         s_tack_int stk1;
         int f_lag;
         binary_node_stk *tempo=bst_root;

        do
        {
            if(tempo!=NULL)
            {
                stk.bst_push(tempo);
                stk1.bst_push(1);
                tempo=tempo->left_subtree;
            }
            else
            {
                if(stk.empty( ))
                    break;
                tempo=stk.bst_pop( );
                f_lag=stk1.bst_pop( );
                if(f_lag==2)
                {
                    cout<<tempo->bst_data;
                    tempo=NULL;
                } /*end if */
                else
                {
                    stk.bst_push(tempo);
                    stk1.bst_push(2);
                    tempo=tempo->right_subtree;
                } 
            } 
        }while(1);
}

void bin_src_tree::print_inorder_rec( )
{
     cout<<" ";
     inorder_rec(bst_root);
     cout<<" ";
}

void bin_src_tree::print_inorder_non_rec( )
{
    cout<<" ";
    inorder_non_rec(bst_root);
    cout<<" ";
}

void bin_src_tree::print_preorder_rec( )
{
    cout<<" ";
    preorder_rec(bst_root);
    cout<<" ";
}

void bin_src_tree::print_preorder_non_rec( )
{
    cout<<" ";
    preorder_non_rec(bst_root);
    cout<<" ";
}

void bin_src_tree::print_postorder_rec( )
{
    cout<<" ";
    postorder_rec(bst_root);
    cout<<" ";
}

void bin_src_tree::print_postorder_non_rec( )
{
    cout<<" ";
    postorder_non_rec(bst_root);
    cout<<" ";
}

int main( )
{
    bin_src_tree B_S_T;
    int chh,e_lement;
    

    do
    {
        cout<<" 1. Press 1 tp insert a node in binary tree"<<endl;
        cout<<" 2. Press 2 for recursive inorder traversal"<<endl;
        cout<<" 3. Press 3 for non recursive inorder traversal"<<endl;
        cout<<" 4. Press 4 for recursive preorder traversal"<<endl;
        cout<<" 5. Press 5 non recursive preorder traversal"<<endl;
        cout<<" 6. Press 6 recursive postorder traversal"<<endl;
        cout<<" 7. Press 7 non recursive postorder traversal"<<endl;
        cout<<" 8. Press 8 to exit"<<endl;
        cout<<" Please enter your choice"<<endl;
        cin>>chh;

        switch(chh)
        {
            case 1:
                    cout<<" Enter the value of node that you want to insert"<<endl;
                    cin>>e_lement;
                    B_S_T.insert(e_lement);
                    break;
            case 2:
                    cout<<" This is recursive inorder traversal"<<endl;
                    B_S_T.print_inorder_rec( );
                    break;
            case 3:
                    cout<<" This is non recursive inorder traversal"<<endl;
                    B_S_T.print_inorder_non_rec( );
                    break;
            case 4:
                    cout<<" This is recursive preorder traversal"<<endl;
                    B_S_T.print_preorder_rec( );
                    break;
            case 5:
                    cout<<" This is non recursive preorder traversal"<<endl;
                    B_S_T.print_preorder_non_rec( );
                    break;
            case 6:
                    cout<<" This is recursive postorder traversal"<<endl;
                    B_S_T.print_postorder_rec( );
                    break;
            case 7:
                    cout<<" This is non recursive postorder traversal"<<endl;
                    B_S_T.print_postorder_non_rec( );
                    break;
            case 8:
                    exit(1);

        }
    }while(chh<8);
}
Output:

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

6

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

5

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

7

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

4

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

8

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

3

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

9

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

1

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

1

 Enter the value of node that you want to insert

10

 1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

2

 This is recursive inorder traversal

 1	3	4	5	6	7	8	9	10	  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

3

 This is non recursive inorder traversal

 1	3	4	5	6	7	8	9	10	  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

4

 This is recursive preorder traversal

 6	5	4	3	1	7	8	9	10	  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

4 5

 This is non recursive preorder traversal

 6	5	4	3	1	7	8	9	10	  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

6

 This is recursive postorder traversal

 1	3	4	5	10	9	8	7	6	  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

7

 This is non recursive postorder traversal

 1345109876  1. Press 1 tp insert a node in binary tree

 2. Press 2 for recursive inorder traversal

 3. Press 3 for non recursive inorder traversal

 4. Press 4 for recursive preorder traversal

 5. Press 5 non recursive preorder traversal

 6. Press 6 recursive postorder traversal

 7. Press 7 non recursive postorder traversal

 8. Press 8 to exit

 Please enter your choice

8
Code Analysis:
The above code performs Binary search tree operation using Stack data structure. Time complexity of the programs depends on the type of data structures used. In the above code Stack data structure is used. Time complexity of push operation in stack takes O(1) time and pop operation in Stack takes O(n) time (if the last element of the stack is to be popped).

In case Linked List data structure, inserting an element in the linked list takes O(n) time complexity whereas deleting an element in the linked list takes O(1) time complexity.