Program to implement Binary Search Tree operations

// Program to implement Binary Search Tree operations

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

class BinarySearchTree
{
    private:
	struct tree_node
	{
	   tree_node* left;
	   tree_node* right;
	   int data;
	};
	tree_node * root, *curr, *parent;
	int dir;
    public:
	BinarySearchTree()
	{
	   root = NULL;
	}
	int isEmpty()
	{
		if(root==NULL)
			return 1;
		else
			return 0;
	}
	void print_inorder();
	void inorder(tree_node*);
	void insert(int);
	void remove(int);
	int search(int);
};

int BinarySearchTree::search(int d)
{
    curr = root;
	while(curr != NULL)
    {
	 if(curr->data == d)
	    return 1;
	 else
	 {
	     parent = curr;
	     if(d>curr->data)
	     {
		curr = curr->right;
		dir=2;
		 }
	     else
	     {
		curr = curr->left;
		dir=1;
	     }
	 }
    }
	return 0;
	}

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
	parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr;
    curr = root;
    // Find the Node's parent
	while(curr)
    {
	parent = curr;
	if(t->data > curr->data)
		curr = curr->right;
	else
		curr = curr->left;
	}

	if(t->data < parent->data)
	   parent->left = t;
	else
	   parent->right = t;
  }
}

void BinarySearchTree::remove(int d)
{
		if(search(d))
		{

			tree_node *q,*pred,*succ;

			if(root->data==d)
			{
				parent=NULL;
				curr=root;
			}
			if(curr->left==NULL && curr->right==NULL)
				q=NULL;
			else if(curr->left==NULL && curr->right!=NULL)
				q=curr->right;
			else if(curr->left!=NULL && curr->right==NULL)
				q=curr->left;
			else
			{
				q=curr->right;

				if(q->left==NULL)
					q->left=curr->left;
				else
				{
					pred=q;
					succ=q->left;
					while(succ->left!=NULL)
					{
						pred=succ;
						succ=succ->left;
					}
					pred->left=succ->right;
					q=succ;
					q->left=curr->left;
					q->right=curr->right;
				}
			}

			if(parent==NULL)
				root=q;
			else if(dir==1)
				parent->left=q;
			else
				parent->right=q;

			cout<<" After Removal tree is: "<<endl;
			print_inorder();

			}
		else
			cout<<"\nElement not found";
}


void BinarySearchTree::print_inorder()
{
  if(root)
	  inorder(root);
  else
	cout<<"\nTree empty";
}

void BinarySearchTree::inorder(tree_node* p)
{
	if(p)
	{
		inorder(p->left);
		cout<<" "<<p->data<<" ";
		inorder(p->right);
	}
}

void main()
{
	BinarySearchTree b;
	int ch,tmp,tmp1;
	clrscr();
	while(1)
	{
	   cout<<endl<<endl;
	   cout<<" Binary Search Tree Operations "<<endl;
	   cout<<" ----------------------------- "<<endl;
	   cout<<" 1. Insertion/Creation "<<endl;
	   cout<<" 2. Removal "<<endl;
	   cout<<" 3. Search "<<endl;
	   cout<<" 4. Exit "<<endl;
	   cout<<" \nEnter your choice : ";
	   cin>>ch;
	   switch(ch)
	   {
	   case 1 :
			cout<<" Enter Number to be inserted : ";
			cin>>tmp;
			b.insert(tmp);
			cout<<" After Insertion tree is: ";
			b.print_inorder();
			break;
	   case 2 :
			if(b.isEmpty())
				cout<<"Tree empty";
			else
			{
				cout<<" Enter data to be deleted : ";
				cin>>tmp1;
				b.remove(tmp1);
			}
			break;
	   case 3 :
			if(b.isEmpty())
				cout<<"\nTree Empty";
			else
			{
				cout<<"\nEnter data to search :";
				cin>>tmp1;
				if(b.search(tmp1))
					cout<<"\nElement found";
				else
					cout<<"\nElement not found";
			}
			break;
	   case 4:
			exit(0);
       }
    }
}