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);
    }
}