//Binary Tree Traversals - Recursive & Non-Recursive
//		 Gaurang Sinha
//	    gaurang85@rediffmail.com
//   gaurang.cjb.net -or- gaurang85.tripod.com
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct tree
	{
		int pos;
		char data;
		struct tree *left,*right;
	}TREE;
TREE *p,*start,*stack[20];

//Functions Using Recursion
void add(TREE *root),preorder(TREE *root);
void postorder(TREE *root),inorder(TREE *root);

//Functions & Variables Not Using Recursion
int dep,Position,*visited;
void dispIn(TREE *root),dispPre(TREE *root),dispPost(TREE *root);


int main()
{
int s;
char data;
A:
clrscr();
printf( "\n\t\t  MENU"
	"\n\t\t1 ADD TO TREE"
	"\n\t\t2 DISPLAY USING RECURSION"
	"\n\t\t3 DISPLAY WITHOUT RECURSION"
	"\n\t\t4 EXIT"
	"\n\t\t::> ");
scanf("%d",&s);
switch(s)
{
case 1:
	p=malloc(sizeof(struct tree));
	printf("\nEnter Element : ");
	p->pos=Position;
	Position++;
	p->data=getche();
	p->left=NULL;p->right=NULL;
	if(start==NULL)
		start=p;
	else
		add(start);
	goto A;
case 2:
	printf("\n\n\t\tBinary Tree : ");
	printf("\n\tInOrder   : ");
	inorder(start);
	printf("\n\tPreOrder  : ");
	preorder(start);
	printf("\n\tPostOrder : ");
	postorder(start);
	getch();
	goto A;
case 3:
	printf("\n\n\t\tBinary Tree Without Recursion");
	printf("\n\tPreOrder  : ");
	dispPre(start);
	printf("\n\tInOrder   : ");
	dispIn(start);
	printf("\n\tPostOrder : ");
	dispPost(start);
	getch();
	goto A;
case 4:
	return 0;
default:
	goto A;
}
}

void add(struct tree *root)
{
int s;
printf("\n\t1. Left\n\t2. Right\n\t::>");
scanf("%d",&s);
if(s==1)
{
	if(root->left==NULL)
		root->left=p;
	else
		add(root->left);
}
else
{
	if(root->right==NULL)
		root->right=p;
	else
		add(root->right);
}
}

void inorder(struct tree *root)
{
if(root!=NULL)
{
	inorder(root->left);
	printf(" %c ",root->data);
	inorder(root->right);
}
}

void preorder(struct tree *root)
{
if(root!=NULL)
{
	printf(" %c ",root->data);
	preorder(root->left);
	preorder(root->right);
}
}

void postorder(struct tree *root)
{
if(root!=NULL)
{
	postorder(root->left);
	postorder(root->right);
	printf(" %c ",root->data);
}
}


void dispIn(TREE *root)
{
dep=0;
while(root!=NULL)
{
	while(root!=NULL)
	{
		stack[dep]=root;
		dep++;
		root=root->left;
	}
	root=stack[dep-1];
	dep--;
	while(root!=NULL)
	{
		printf(" %c ",root->data);
		if(root->right!=NULL)
		{
			root=root->right;
			break;
		}
		root=stack[dep-1];
		dep--;
	}
}
}

void dispPre(TREE *root)
{
dep=0;
while(root!=NULL)
{
	while(root!=NULL)
	{
		printf(" %c ",root->data);
		stack[dep]=root;
		dep++;
		root=root->left;
	}
	root=stack[dep-1];
	dep--;
	while(root!=NULL)
	{
		if(root->right!=NULL)
		{
			root=root->right;
			break;
		}
		else
		{
			root=stack[dep-1];
			dep--;
		}
	}

}
}

void dispPost(TREE *root)
{
dep=0;
//Array To Check weather we've already visited those positions
visited=malloc(sizeof(int)*Position);
while(root!=NULL)
{
	while(root!=NULL)
	{
		stack[dep]=root;
		dep++;
		root=root->left;
	}
	root=stack[dep-1];
	dep--;
	if(root->right!=NULL)
	{
		if(visited[root->pos]!=1)
		{
			stack[dep]=root;
			dep++;
			visited[root->pos]=1;
		}
		root=root->right;
	}
	else
	{
		while(root!=NULL)
		{
			if(visited[root->pos]!=1)
			{
				stack[dep]=root;
				dep++;
				visited[root->pos]=1;
				if(root->right!=NULL)
				{
					root=root->right;
					break;
				}
				else
				{
					root=stack[dep-1];
					dep--;
				}
			}
			else
			{
				printf(" %c ",root->data);
				root=stack[dep-1];
				dep--;
			}
		}
	}
}
free(visited);
}