/*
Title Binary Search Tree (with non-recursive traversals) Author Rajeswari Natarajan Author Email raji [at] svce.ac.in Description This program includes the inserting a node, deleting a node,recursive tree traversal,non-recursive tree traversal,finding the
minimum,maximum,leftchild,rightchild,copy a tree to another,making a tree null.
Category C++ » Data Structures Hits 623 

*/

Code :
# include <conio.h>
# include <process.h>
# include <iostream.h>
# include <alloc.h>

struct node
{
	int ele;
	node *left;
	node *right;
};

typedef struct node *nodeptr;
class stack
{
	private:
		struct snode
		{
			nodeptr ele;
			snode *next;
		};
		snode *top;
	public:
		stack()
		{
			top=NULL;
		}
		void push(nodeptr p)
		{
			snode *temp;
			temp = new snode;
			temp->ele = p;
			temp->next = top;
			top=temp;
		}

		void pop()
		{
			if (top != NULL)
			{
			nodeptr t;
			snode *temp;
			temp = top;
			top=temp->next;
			delete temp;
			}
		}

		nodeptr topele()
		{
			if (top !=NULL)
				return top->ele;
			else
				return NULL;
		}



		int isempty()
		{
		return ((top == NULL) ? 1 : 0);
		}

};


class bstree
{
	public:
		void insert(int,nodeptr &);
		void del(int,nodeptr &);
		int deletemin(nodeptr &);
		void find(int,nodeptr &);
		nodeptr findmin(nodeptr);
		nodeptr findmax(nodeptr);
		void copy(nodeptr &,nodeptr &);
		void makeempty(nodeptr &);
		nodeptr nodecopy(nodeptr &);
		void preorder(nodeptr);
		void inorder(nodeptr);
		void postorder(nodeptr);
		void preordernr(nodeptr);
		void inordernr(nodeptr);
		void postordernr(nodeptr);
		void leftchild(int,nodeptr &);
		void rightchild(int,nodeptr &);


};

void bstree::insert(int x,nodeptr &p)
{
	if (p==NULL)
	{
		p = new node;
		p->ele=x;
		p->left=NULL;
		p->right=NULL;
	}
	else
	{
		if (x < p->ele)
			insert(x,p->left);
		else if (x>p->ele)
			insert(x,p->right);
		else
			cout<<"Element already Exits !";
	}
}

void bstree:: del(int x,nodeptr &p)
{
	nodeptr d;
	if (p==NULL)
		cout<<"Element not found ";
	else if (x < p->ele)
		del(x,p->left);
	else if (x > p->ele)
		del(x,p->right);
	else if ((p->left == NULL) && (p->right ==NULL))
	{
		d=p;
		free(d);
		p=NULL;
	}
	 else if (p->left == NULL)
	{
		d=p;
		free(d);
		p=p->right;
	}
	else if (p->right ==NULL)
	{
		d=p;
		p=p->left;
		free(d);
	}
	else
	p->ele=deletemin(p->right);
}

int bstree::deletemin(nodeptr &p)
{
	int c;
	if (p->left == NULL)
	{
		c=p->ele;
		p=p->right;
		return c;
	}
	else
		c=deletemin(p->left);
		return c;
}

void bstree::copy(nodeptr &p,nodeptr &p1)
{
	makeempty(p1);
	p1=nodecopy(p);
}

void bstree::makeempty(nodeptr &p)
{
	nodeptr d;
	if (p!=NULL)
	{
		makeempty(p->left);
		makeempty(p->right);
		d=p;
		free(d);
		p=NULL;
	}
}

nodeptr bstree::nodecopy(nodeptr &p)
{
	nodeptr temp;
	if (p == NULL)
		return p;
	else
	{
		temp = new node;
		temp->ele=p->ele;
		temp->left = nodecopy(p->left);
		temp->right = nodecopy(p->right);
		return temp;
	}
}


nodeptr bstree::findmin(nodeptr p)
{
	if (p==NULL)
	{
		cout<<"Tree is empty !";
		return p;
	}
	else
	{
		while (p->left !=NULL)
			p=p->left;
		return p;
	}
}



nodeptr bstree::findmax(nodeptr p)
{
	if (p==NULL)
	{
		cout<<"Tree is empty !";
		return p;
	}
	else
	{
		while (p->right !=NULL)
			p=p->right;
		return p;
	}
}

void bstree::find(int x,nodeptr &p)
{
	if (p==NULL)
		cout<<"Element not found  !";
	else
	{
		if (x <p->ele)
			find(x,p->left);
		else if ( x> p->ele)
			find(x,p->right);
		else
			cout<<"Element Found !";
	}
}

void bstree::preorder(nodeptr p)
{
	if (p!=NULL)
	{
		cout<<p->ele<<"-->";
		preorder(p->left);
		preorder(p->right);
	}
}
void bstree::inorder(nodeptr p)
{
	if (p!=NULL)
	{
		inorder(p->left);
		cout<<p->ele<<"-->";
		inorder(p->right);
	}
}

void bstree::postorder(nodeptr p)
{
	if (p!=NULL)
	{
		postorder(p->left);
		postorder(p->right);
		cout<<p->ele<<"-->";
	}
}



void bstree::preordernr(nodeptr p)
{
	stack s;
	while (1)
	{
	if  (p != NULL)
	{
		cout<<p->ele<<"-->";
		s.push(p);
		p=p->left;
	}
	else
	if (s.isempty())
	{
		cout<<"Stack is empty";
		return;
	}
	else
	{
		nodeptr t;
		t=s.topele();
		p=t->right;
		s.pop();
	}
	}
}


void bstree::inordernr(nodeptr p)
{
	stack s;
	while (1)
	{
	if  (p != NULL)
	{
		s.push(p);
		p=p->left;
	}
	else
	{
	if (s.isempty())
	{
		cout<<"Stack is empty";
		return;
	}
	else
	{
		p=s.topele();
		cout<<p->ele<<"-->";
	}
	s.pop();
	p=p->right;
	}
	}
}


void bstree::postordernr(nodeptr p)
{
	stack s;
	while (1)
	{
	if  (p != NULL)
	{
		s.push(p);
		p=p->left;
	}
	else
	{
		if (s.isempty())
		{
			cout<<"Stack is empty";
			return;
		}
		else
		if (s.topele()->right == NULL)
		{
			p=s.topele();
			s.pop();
			cout<<p->ele<<"-->";
			if (p==s.topele()->right)
			{
				cout<<s.topele()->ele<<"-->";
				s.pop();
			}
		}
		if (!s.isempty())
			p=s.topele()->right;
		else
			p=NULL;
	}
	}
}

void bstree::leftchild(int q,nodeptr &p)
{
	if (p==NULL)
		cout<<"The node does not exists ";

	else
	if (q < p->ele )
		leftchild(q,p->left);
	else
	if (q > p->ele)
		leftchild(q,p->right);
	else
	if (q == p->ele)
	{
		if (p->left != NULL)
			cout<<"Left child of "<<q<<"is "<<p->left->ele;
		else
			cout<<"No Left child !";
	}
}

void bstree::rightchild(int q,nodeptr &p)
{
	if (p==NULL)
		cout<<"The node does not exists ";
	else
	if (q < p->ele )
		rightchild(q,p->left);
	else
	if (q > p->ele)
		rightchild(q,p->right);
	else
	if (q == p->ele)
	{
		if (p->right != NULL)
			cout<<"Right child of "<<q<<"is "<<p->right->ele;
		else
			cout<<"No Right Child !";
	}
}





int main()
{
int ch,x,leftele,rightele;
bstree bst;
char c='y';
nodeptr root,root1,min,max;
root=NULL;
root1=NULL;
do
{
//	system("clear");
	clrscr();
	cout<<"
Binary Search Tree 
";
	cout<<"-------------------------
";
	cout<<"		1.Insertion
		2.Deletion
		3.NodeCopy
";
	cout<<"		4.Find
		5.Findmax
		6.Findmin
";
	cout<<"		7.Preorder
		8.Inorder
		9.Postorder
";
	cout<<"
		10.Leftchild
		11.Rightchild
		0.Exit
";
	cout<<"
Enter your choice :";
	cin>>ch;

	switch(ch)
	{
	case 1:
		cout<<"
		1.Insertion
";
		cout<<"Enter the new element to get inserted :
";
		cin>>x;

		bst.insert(x,root);
		cout<<"Inorder traversal is :
";
		bst.inorder(root);
		break;

	case 2:
		cout<<"
		2.Deletion
";
		cout<<"Enter the element to get deleted :
";
		cin>>x;
		bst.del(x,root);
		bst.inorder(root);
		break;

	case 3:
		cout<<"
		3.Nodecopy
";
		bst.copy(root,root1);
		cout<<"
The new tree is :
";
		bst.inorder(root1);
		break;

	case 4:
		cout<<"
		4.Find
";
		cout<<"Enter the element to be searched :
";
		cin>>x;
		bst.find(x,root);
		break;

	case 5:
		cout<<"
		5.Findmax
";
		if (root == NULL)
			cout<<"
Tree is empty";
		else
		{
			max=bst.findmax(root);
			cout<<"Largest element is :	"<<max->ele<<endl;
		}
		break;

	case 6:
		cout<<"
		6.Findmin
";
		if (root == NULL)
			cout<<"
Tree is empty";
		else
		{
			min=bst.findmin(root);
			cout<<"Smallest element is :	"<<min->ele<<endl;
		}
		break;

	case 7:
		cout<<"
		7.Preorder
";
		if (root==NULL)
			cout<<"
Tree is empty";
		else
		{
			cout<<"
Preorder traversal (Non-Recursive) is :
";
			bst.preordernr(root);
			cout<<"
Preorder traversal (Recursive) is :
";
			bst.preorder(root);
		}
		break;

	case 8:
		cout<<"
		8.Inorder
";
		if (root==NULL)
			cout<<"
Tree is empty";
		else
		{
			cout<<"
Inorder traversal (Non-Recursive) is :
";
			bst.inordernr(root);
			cout<<"
Inorder traversal (Recursive) is :
";
			bst.inorder(root);
		}
		break;

	case 9:
		cout<<"
		9.Postorder
";
		if (root==NULL)
			cout<<"
Tree is empty";
		else
		{
			cout<<"
Postorder traversal (Non-Recursive) is :
";
			bst.postordernr(root);
			cout<<"
Postorder traversal (Recursive) is :
";
			bst.postorder(root);
		}
		break;

	case 10:
		cout<<"
		10.Finding the left Child 
";
		if (root==NULL)
			cout<<"
Tree is empty";
		else
		{
			cout<<"Enter the node for which the left child is to be found :
";
			cin>>leftele;
			bst.leftchild(leftele,root);
		}
		break;

	case 11:
		cout<<"
		11.Finding the Right Child 
";
		if (root==NULL)
			cout<<"
Tree is empty";
		else
		{
			cout<<"Enter the node for which the Right child is to be found :
";
			cin>>rightele;
			bst.rightchild(rightele,root);
		}
		break;


	case 0:
		exit(0);
	}
	cout<<"
Continue (y/n) ?
";
	cin>>c;
	}while (c=='y' || c == 'Y');
	return 0;
}