//	Author:		Mohammed Ali Akbani
//This program creates and manages a binary tree data structure. Lower values
//are at left node. To test program don't enter data in alphabetical order

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>


//Defination of nodes of the tree
class node
{
	public:
		  char value [11];
		  node *lchild;
		  node *rchild;
};

node  *root = NULL;	//root note is set to empty


//INSERT A NEW NODE IN THE TREE
void insert (node *z)
{

	node *x;
	node *y;

	y = NULL;
	x = root;

	while ( x!=NULL)
	{
		y = x;

		 //compare value of new node with value of x
		if(strcmp(z->value,x->value) < 0)
		{
			x= x-> lchild; //if new value less seek left child
		}
		else
		{
			x= x-> rchild; //if new value greater seek right child
		}
	}

	//if value of y is null write new node at root
	if( y==NULL )
	{
		root=z;
	}
	else	if(strcmp( z->value,y->value) < 0)
		{
			y -> lchild = z;
		}
		else
		{
			y-> rchild = z;
		}
}


//PREORDER TRAVERSAL OF TREE BY RECURSION
void preorder( node *r )
{
	cout<< r -> value << " ";

	if (r->lchild != NULL)
		preorder (r->lchild);

	if (r->rchild != NULL)
		preorder (r->rchild);
}


//INORDER TRAVERSAL OF TREE BY RECURSION
void inorder( node *r )
{
	if (r->lchild != NULL)
		inorder (r->lchild);

	cout<< r -> value << " ";

	if (r->rchild != NULL)
		inorder (r->rchild);
}


//POSTORDER TRAVERSAL OF TREE BY RECURSION
void postorder( node *r )
{
	if (r->lchild != NULL)
		postorder (r->lchild);

	if (r->rchild != NULL)
		postorder (r->rchild);

	cout<< r -> value << " ";

}


void main()
{
	int choice;
	while (choice!=3)
	{
		clrscr();

		cout<<"\n\n\t 1. Insert a element to the tree.";
		cout<<"\n\n\t 2. Traverse the tree.";
		cout<<"\n\n\t 3. Exit.";
		cout<<"\n\n\t Enter your choice :  ";
		cin>>choice;

		switch (choice)
		{

			case 1: clrscr();
				node *z=new node; //create a new node

				cout<<"\n\n\tEnter a text string: ";
				cin >> z->value;

				z->rchild=NULL; //set left child as NULL
				z->lchild=NULL; //set right child as NULL

				insert (z); //insert node in tree
				break;

			case 2: clrscr();
				cout << "\n\n\t Preorder Traversal : ";
				preorder(root);

				cout << "\n\n\t Inorder Traversal : ";
				inorder(root);

				cout << "\n\n\t Postorder Traversal : ";
				postorder(root);

				getch();
				break;

			case 3: break;
		}
       }
}
// end of program