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

int smat[100];int z;
struct record;
typedef record* ptr ;
struct record
{
	int data;
	ptr left,right;
};

ptr root,node,back,tempback;
char choice;
int found=0,delno;

void additem(ptr& p,int n)
{
	if (p==NULL)
	{
		p=new(record);
		p->left=NULL;
		p->right=NULL;
		p->data=n;
	}
	else
	if (n>p->data) additem(p->right,n);
	else additem(p->left,n);
}

void display1(ptr p)
{
	if (p!=NULL)
	{
		display1(p->left);
		cout << p->data << " ";
		display1(p->right);
	}
}

void display2(ptr p)
{
	if (p!=NULL)
	{
		cout << p->data << " ";
		display2(p->left);
		display2(p->right);
	}
}

void display3(ptr p)
{
	if (p!=NULL)
	{
		display3(p->left);
		display3(p->right);
		cout << p->data << " ";
	}
}

void search(ptr p,int n)
{
	if (p!=NULL)
	{
		if (p->data==n) {found=1;node=p;back=tempback;}
		tempback=p;
		search(p->left,n);
		search(p->right,n);
	}
}

void create()
{
	int n;
	printf("Start creating the tree\nPress 0 to stop\n");
	do
	{
		cin >> n;
		if (n==0) break;
		additem(root,n);
	} while(1);
}

void add()
{
	printf("Enter the data to add: ");
	int n;
	cin >> n;
	additem(root,n);
}

void del(int n)
{
	ptr ext,extback;
	search(root,n);
	ext=node;
	extback=back;
	cout << ext->data << extback->data << " ";
	while(ext->right!=NULL)
	{
		extback=ext;
		ext=ext->right;
	}

	back->left=ext;
	extback->right=NULL;
	ext->left=node->left;

	//cout << ext->data << extback->data;

}

void deltree(ptr p)
{
	if (p!=NULL)
	{
		deltree(p->left);
		deltree(p->right);
		delete p;
	}
}

void getsortedmat(ptr p)
{
	if (p!=NULL)
	{
		getsortedmat(p->left);
		smat[z]=p->data;
		z++;
		getsortedmat(p->right);
	}
}

void balance(int x,int y)
{
	int currroot=0,index=0,m=0,o=0,n=0;
	if(x>=y) additem(root,smat[x]);else
	if(y>x)
	{
		n=y-x+1;
		m=n%2;
		o=x+n/2;
		//o=n/2;
		if(m==0)
		{
			currroot=smat[o-1];
				index=o-1;
		}
		else
		{
			currroot=smat[o];
			index=o;
		}
		additem(root,currroot);
		if(index!=x) balance(x,index-1);
		if(index!=y) balance(index+1,y);
	}
}

void menu()
{
	printf("\n\na:add,s:search,1,2,3:display,d:delete,x:exit : ");
	cin >> choice;
	switch (toupper(choice))
	{
		case 'A':add();break;
		case '1':display1(root);break;
		case '2':display2(root);break;
		case '3':display3(root);break;
		case 'D':
				 getsortedmat(root);
				 z--;
				 deltree(root);
				 root=NULL;
				 balance(0,z);
				 break;
		case 'S':{
					int finddata;
					printf("\nEnter the data to find: ");
					cin >> finddata;
					found=0;
					search(root,finddata);
					if(found==1) printf("%d found",finddata);
					else printf("%d not found",finddata);
					found=0;
				 }break;
	}
}

int main()
{
	clrscr();
	root=NULL;
	create();
	do
	{
		menu();
	} while (choice!='x');
	return 0;
}