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

static int G=0;

void node_draw(float,int);
void valuecompare(int,int);

struct node
{
node *LeftChild;
node *RightChild;
int  data;
};

struct compare
{
float poscheck;
int getval;
};

class tree
{
private:

node *root,
	  *parent,
	  *p_parent;


void preorder(node *currentnode)
{
if(currentnode)
{
valuecompare(currentnode->data, WHITE);
preorder(currentnode->LeftChild);
preorder(currentnode->RightChild);
}
}

void inorder(node *currentnode)
{
if(currentnode)
{
inorder(currentnode->LeftChild);
valuecompare(currentnode->data, RED);
inorder(currentnode->RightChild);
}
}

void postorder(node *currentnode)
{
if(currentnode)
{
postorder(currentnode->LeftChild);
postorder(currentnode->RightChild);
valuecompare(currentnode->data,2);
}
}

public:

tree()
{
	 root = NULL;
  parent = NULL;
}

void insert(int x)
{
float left=0;
float right=0,send=0;
  parent = root;
p_parent = NULL;

if(x<root->data)
{

while(parent)
{
p_parent = parent;

if(x < parent->data)
{
parent = parent -> LeftChild;
left=left+10;
}
else
{
parent = parent -> RightChild;
left=left/4;
}
}
}

else
{
while(parent)
{
p_parent = parent;

if(x < parent->data)
{
parent = parent -> LeftChild;
right=right/4;
}
else
{
parent = parent -> RightChild;
right=right+75;
}
}
}
parent = new node;
parent -> LeftChild = NULL;
parent -> RightChild = NULL;
parent -> data = x;


if(!root)
{
root = parent;
}
else if(x < p_parent -> data)
{
p_parent -> LeftChild = parent;
}
else
{
p_parent -> RightChild = parent;
}


if(left==0 && right !=0)
{
send=right;
}
else
{
send=left;
}
node_draw(send,x);
}

void Preorder(void)
{
preorder(root);
}

void Inorder(void)
{
inorder(root);
}

void Postorder(void)
{
postorder(root);
}

};


void main(void)
{
	int gdriver = DETECT, gmode, errorcode;
	initgraph(&gdriver, &gmode, "..\\bgi");
	errorcode = graphresult();
	if (errorcode != grOk)
	{
		cout<<"Graphics error: "<<grapherrormsg(errorcode)<<endl;
		cout<<"Press any key to halt:";
		getch();
		exit(1);
	}

char ans;
int n;
int array[31];
tree t;

t.insert(200);
t.insert(180);
t.insert(150);
t.insert(400);
t.insert(385);
t.insert(140);
t.insert(390);
t.insert(395);
t.insert(130);
t.insert(190);
t.insert(382);
t.insert(195);
t.insert(199);
t.insert(187);
t.insert(450);
t.insert(425);
t.insert(410);
t.insert(383);
t.insert(169);
t.insert(188);
t.insert(470);
t.insert(194);
t.insert(460);
t.insert(381);
t.insert(184);
t.insert(490);
t.insert(389);
t.insert(145);
t.insert(165);
t.insert(430);
t.insert(170);


/*
while(ans!='n' && ctr<=30)
{
gotoxy(1,1);
cout<<"Enter value number "<<ctr<<" ";
cin>>n;

for(int i=0; i<=30; i++)
{
if(n==array[i])
{
flag=1;
}
}

if(flag)
{
gotoxy(1,2);
cout<<"Value is matching with a previously entered value...Re-Enter ";
flag=0;
}
else
{
array[ctr++]=n;
t.insert(n);
}
gotoxy(1,4);
cout<<"Do you want to enter more ( y , n ) ? ";
ans=getche();
}
*/
int choice;

do
{
settextstyle(2,0,5);
setcolor(YELLOW);
outtextxy(10,4,"What traversing you want ? ___");
setcolor(10);
outtextxy(10,20,"[1] Preorder");
outtextxy(10,34,"[2] Inorder");
outtextxy(10,48,"[3] Postorder");
setcolor(13);
outtextxy(10,62,"[4] Exit Program");

gotoxy(29,1);
cin>>choice;

settextstyle(12,0,1);
switch(choice)
{
case 1:
t.Preorder();
break;

case 2:
t.Inorder();
break;

case 3:
t.Postorder();
break;

case 4:
exit(0);
break;
}
gotoxy(29,1);
cout<<"  ";

setcolor(10);
settextstyle(2,0,6);
outtextxy(120,430,"Do you want to do more traversing ? (y / n) ");
ans=getche();
if(ans!='n')
{
setcolor(16);
settextstyle(2,0,6);
outtextxy(120,430,"Do you want to do more traversing ? (y / n) ");
setcolor(11);
outtextxy(120,450,"Please re-enter any choice from the above menu");
}
}while(ans!='n');
closegraph();
}


compare bothstore[31];

void node_draw(float position, int val)
{
settextstyle(2,0,5);
setcolor(YELLOW);
outtextxy(400,20,"By ___ Osman Khalid ( MCS )");
settextstyle(12,0,1);

bothstore[G].poscheck=position;
bothstore[G].getval=val;
G++;

char value[5];

for(int i=0; i<=4; i++){value[i]=NULL;}

if(position==0)
{
setcolor(11);
setfillstyle(11, 12);
circle(321,17,17);
floodfill(321, 17, 11);
sprintf(value,"%d",val);
setcolor(WHITE);
outtextxy(310,12,value);
}


// Level 1
else if(position==10)
{
setcolor(10);
line(322,35,165,115);
setcolor(14);
circle(157,130,17);
sprintf(value,"%d",val);
outtextxy(146,125,value);
}


else if(position==75)
{
setcolor(12);
line(322,35,470,115);
setcolor(13);
circle(480,130,17);        /////////// right
sprintf(value,"%d",val);
outtextxy(469,125,value);
}


// Level 2

else if(position==20)
{
setcolor(10);
line(158,148,80,183);
setcolor(14);
circle(77,200,17);
sprintf(value,"%d",val);
outtextxy(66,195,value);
}


else if(position==2.5)
{
setcolor(10);
line(158,148,230,183);
setcolor(14);
circle(235,200,17);
sprintf(value,"%d",val);
outtextxy(224,195,value);
}


else if(position==18.75)
{
setcolor(12);
line(481,148,400,183);
setcolor(13);
circle(402,200,17);
sprintf(value,"%d",val);
outtextxy(391,195,value);
}

else if(position==150)
{
setcolor(12);
line(481,148,560,183);
setcolor(13);
circle(560,200,17);
sprintf(value,"%d",val);
outtextxy(549,195,value);
}

//Level 3
////////////////////////// Right Row ////////////////////

else if(position==30)
{
setcolor(10);
line(78,218,40,282);
setcolor(14);
circle(37, 300,17);
sprintf(value,"%d",val);
outtextxy(26,295,value);
}

else if(position==5)
{
setcolor(10);
line(78,218,115,282);
setcolor(14);
circle(117,300,17);
sprintf(value,"%d",val);
outtextxy(106,295,value);
}

else if(position==12.5)
{
setcolor(10);
line(236,218,195,282);
setcolor(14);
circle(197,300,17);
sprintf(value,"%d",val);
outtextxy(186,295,value);
}

else if(position==.625)
{
setcolor(10);
line(236,218,275,282);
setcolor(14);
circle(277,300,17);
sprintf(value,"%d",val);
outtextxy(266,295,value);
}
////////////////////////// Left Row //////////////////////

else if(position==4.6875)
{
setcolor(12);
line(403,218,365,282);
setcolor(13);
circle(363,300,17);
sprintf(value,"%d",val);
outtextxy(352,295,value);
}

else if(position==93.75)
{
setcolor(12);
line(403,218,440,282);
setcolor(13);
circle(443,300,17);
sprintf(value,"%d",val);
outtextxy(432,295,value);
}

else if(position==37.5)
{
setcolor(12);
line(561,218,525,282);
setcolor(13);
circle(523,300,17);
sprintf(value,"%d",val);
outtextxy(512,295,value);
}

else if(position==225)
{
setcolor(12);
line(561,218,600,282);
setcolor(13);
circle(603,300,17);
sprintf(value,"%d",val);
outtextxy(592,295,value);
}

// Level 4
else if(position==40)
{
setcolor(10);
line(36,318,16,382);
setcolor(14);
circle(17,400,17);
sprintf(value,"%d",val);
outtextxy(6,395,value);
}

else if(position==7.5)
{
setcolor(10);
line(38,318,55,382);
setcolor(14);
circle(56,400,17);
sprintf(value,"%d",val);
outtextxy(45,395,value);
}

else if(position==15)
{
setcolor(10);
line(116,318,94,382);
setcolor(14);
circle(96,400,17);
sprintf(value,"%d",val);
outtextxy(85,395,value);
}

else if(position==1.25)
{
setcolor(10);
line(116,318,135,382);
setcolor(14);
circle(136,400,17);
sprintf(value,"%d",val);
outtextxy(125,395,value);
}

else if(position==22.5)
{
setcolor(10);
line(196,318,176,382);
setcolor(14);
circle(176,400,17);
sprintf(value,"%d",val);
outtextxy(165,395,value);
}

else if(position==3.125)
{
setcolor(10);
line(196,318,210,382);
setcolor(14);
circle(216,400,17);
sprintf(value,"%d",val);
outtextxy(205,395,value);
}

else if(position==10.625)
{
setcolor(10);
line(276,318,255,382);
setcolor(14);
circle(256,400,17);
sprintf(value,"%d",val);
outtextxy(245,395,value);
}

else if(position==.15625)
{
setcolor(10);
line(276,318,294,382);
setcolor(14);
circle(296,400,17);
sprintf(value,"%d",val);
outtextxy(285,395,value);
}

else if(position==1.171875)
{
setcolor(12);
line(362,318,340,382);
setcolor(13);
circle(343,400,17);
sprintf(value,"%d",val);
outtextxy(332,395,value);
}

else if(position==79.6875)
{
setcolor(12);
line(362,318,380,382);
setcolor(13);
circle(383,400,17);
sprintf(value,"%d",val);
outtextxy(372,395,value);
}

else if(position==23.4375)
{
setcolor(12);
line(442,318,422,382);
setcolor(13);
circle(423,400,17);
sprintf(value,"%d",val);
outtextxy(412,395,value);
}

else if(position==168.75)
{
setcolor(12);
line(442,318,460,382);
setcolor(13);
circle(463,400,17);
sprintf(value,"%d",val);
outtextxy(452,395,value);
}

else if(position==9.375)
{
setcolor(12);
line(522,318,500,382);
setcolor(13);
circle(503,400,17);
sprintf(value,"%d",val);
outtextxy(492,395,value);
}

else if(position==112.5)
{
setcolor(12);
line(522,318,540,382);
setcolor(13);
circle(543,400,17);
sprintf(value,"%d",val);
outtextxy(532,395,value);
}

else if(position==56.25)
{
setcolor(12);
line(602,318,580,382);
setcolor(13);
circle(583,400,17);
sprintf(value,"%d",val);
outtextxy(572,395,value);
}

else if(position==300)
{
setcolor(12);
line(602,318,620,382);
setcolor(13);
circle(622,400,17);
sprintf(value,"%d",val);
outtextxy(611,395,value);
}
getch();
}



void valuecompare(int val, int color)
{
int j=0;
float position=0;

for(int i=0; i<=30; i++)
{
if(val==bothstore[i].getval)
{
j=i;
}
}

position=bothstore[j].poscheck;
char value[5];

for(i=0; i<=4; i++){value[i]=NULL;}

if(position==0)
{
setcolor(color);
setfillstyle(11, color);
circle(321,17,17);
floodfill(321, 17, color);
sprintf(value,"%d",val);
setcolor(WHITE);
outtextxy(310,12,value);
}

// Level 1
else if(position==10)
{
setcolor(10);                          //left line 10 right line 11
line(322,35,165,115);
setcolor(color);
circle(157,130,17);
sprintf(value,"%d",val);
outtextxy(146,125,value);
}


else if(position==75)
{
setcolor(12);
line(322,35,470,115);
setcolor(color);
circle(480,130,17);        /////////// right
sprintf(value,"%d",val);
outtextxy(469,125,value);
}


// Level 2

else if(position==20)
{
setcolor(10);
line(158,148,80,183);
setcolor(color);
circle(77,200,17);
sprintf(value,"%d",val);
outtextxy(66,195,value);
}


else if(position==2.5)
{
setcolor(10);
line(158,148,230,183);
setcolor(color);
circle(235,200,17);
sprintf(value,"%d",val);
outtextxy(224,195,value);
}


else if(position==18.75)
{
setcolor(12);
line(481,148,400,183);
setcolor(color);
circle(402,200,17);
sprintf(value,"%d",val);
outtextxy(391,195,value);
}

else if(position==150)
{
setcolor(12);
line(481,148,560,183);
setcolor(color);
circle(560,200,17);
sprintf(value,"%d",val);
outtextxy(549,195,value);
}

//Level 3
////////////////////////// Right Row ////////////////////

else if(position==30)
{
setcolor(10);
line(78,218,40,282);
setcolor(color);
circle(37, 300,17);
sprintf(value,"%d",val);
outtextxy(26,295,value);
}

else if(position==5)
{
setcolor(10);
line(78,218,115,282);
setcolor(color);
circle(117,300,17);
sprintf(value,"%d",val);
outtextxy(106,295,value);
}

else if(position==12.5)
{
setcolor(10);
line(236,218,195,282);
setcolor(color);
circle(197,300,17);
sprintf(value,"%d",val);
outtextxy(186,295,value);
}

else if(position==.625)
{
setcolor(10);
line(236,218,275,282);
setcolor(color);
circle(277,300,17);
sprintf(value,"%d",val);
outtextxy(266,295,value);
}
////////////////////////// Left Row //////////////////////

else if(position==4.6875)
{
setcolor(12);
line(403,218,365,282);
setcolor(color);
circle(363,300,17);
sprintf(value,"%d",val);
outtextxy(352,295,value);
}

else if(position==93.75)
{
setcolor(12);
line(403,218,440,282);
setcolor(color);
circle(443,300,17);
sprintf(value,"%d",val);
outtextxy(432,295,value);
}

else if(position==37.5)
{
setcolor(12);
line(561,218,525,282);
setcolor(color);
circle(523,300,17);
sprintf(value,"%d",val);
outtextxy(512,295,value);
}

else if(position==225)
{
setcolor(12);
line(561,218,600,282);
setcolor(color);
circle(603,300,17);
sprintf(value,"%d",val);
outtextxy(592,295,value);
}

// Level 4
else if(position==40)
{
setcolor(10);
line(36,318,16,382);
setcolor(color);
circle(17,400,17);
sprintf(value,"%d",val);
outtextxy(6,395,value);
}

else if(position==7.5)
{
setcolor(10);
line(38,318,55,382);
setcolor(color);
circle(56,400,17);
sprintf(value,"%d",val);
outtextxy(45,395,value);
}

else if(position==15)
{
setcolor(10);
line(116,318,94,382);
setcolor(color);
circle(96,400,17);
sprintf(value,"%d",val);
outtextxy(85,395,value);
}

else if(position==1.25)
{
setcolor(10);
line(116,318,135,382);
setcolor(color);
circle(136,400,17);
sprintf(value,"%d",val);
outtextxy(125,395,value);
}

else if(position==22.5)
{
setcolor(10);
line(196,318,176,382);
setcolor(color);
circle(176,400,17);
sprintf(value,"%d",val);
outtextxy(165,395,value);
}

else if(position==3.125)
{
setcolor(10);
line(196,318,210,382);
setcolor(color);
circle(216,400,17);
sprintf(value,"%d",val);
outtextxy(205,395,value);
}

else if(position==10.625)
{
setcolor(10);
line(276,318,255,382);
setcolor(color);
circle(256,400,17);
sprintf(value,"%d",val);
outtextxy(245,395,value);
}

else if(position==.15625)
{
setcolor(10);
line(276,318,294,382);
setcolor(color);
circle(296,400,17);
sprintf(value,"%d",val);
outtextxy(285,395,value);
}

else if(position==1.171875)
{
setcolor(12);
line(362,318,340,382);
setcolor(color);
circle(343,400,17);
sprintf(value,"%d",val);
outtextxy(332,395,value);
}

else if(position==79.6875)
{
setcolor(12);
line(362,318,380,382);
setcolor(color);
circle(383,400,17);
sprintf(value,"%d",val);
outtextxy(372,395,value);
}

else if(position==23.4375)
{
setcolor(12);
line(442,318,422,382);
setcolor(color);
circle(423,400,17);
sprintf(value,"%d",val);
outtextxy(412,395,value);
}

else if(position==168.75)
{
setcolor(12);
line(442,318,460,382);
setcolor(color);
circle(463,400,17);
sprintf(value,"%d",val);
outtextxy(452,395,value);
}

else if(position==9.375)
{
setcolor(12);
line(522,318,500,382);
setcolor(color);
circle(503,400,17);
sprintf(value,"%d",val);
outtextxy(492,395,value);
}

else if(position==112.5)
{
setcolor(12);
line(522,318,540,382);
setcolor(color);
circle(543,400,17);
sprintf(value,"%d",val);
outtextxy(532,395,value);
}

else if(position==56.25)
{
setcolor(12);
line(602,318,580,382);
setcolor(color);
circle(583,400,17);
sprintf(value,"%d",val);
outtextxy(572,395,value);
}

else if(position==300)
{
setcolor(12);
line(602,318,620,382);
setcolor(color);
circle(622,400,17);
sprintf(value,"%d",val);
outtextxy(611,395,value);
}
getch();
}