#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
	int data;
	struct node *left;
	struct node *right;
};

struct node *tree;

void create_tree(struct node *);
struct node *insertElement(struct node *, int);
void preorderTraversal(struct node *);
void inorderTraversal(struct node *);
void postorderTraversal(struct node *);
struct node *findSmallestElement(struct node *);
struct node *findLargestElement(struct node *);
struct node *deleteElement(struct node *, int);
struct node *mirrorImage(struct node *);
int totalNodes(struct node *);
int totalExternalNodes(struct node *);
int totalInternalNodes(struct node *);
int Height(struct node *);
struct node *deleteTree(struct node *);

int main()
{
	int option, val;
	struct node *ptr;
	create_tree(tree);
	do
	{
		printf("\n ******MAIN MENU******* \n");
		printf("\n 1. Insert Element");
		printf("\n 2. Preorder Traversal");
		printf("\n 3. Inorder Traversal");
		printf("\n 4. Postorder Traversal");
		printf("\n 5. Find the smallest element");
		printf("\n 6. Find the largest element");
		printf("\n 7. Delete an element");
		printf("\n 8. Count the total number of nodes");
		printf("\n 9. Count the total number of external nodes");
		printf("\n 10. Count the total number of internal nodes");
		printf("\n 11. Determine the height of the tree");
		printf("\n 12. Find the mirror image of the tree");
		printf("\n 13. Delete the tree");
		printf("\n 14. Exit");
		printf("\n\n Enter your option : ");
		scanf("%d", &option);
		switch(option)
		{
			case 1:
				printf("\n Enter the value of the new node : ");
				scanf("%d", &val);
				tree = insertElement(tree, val);
				break;
			case 2:
				printf("\n The elements of the tree are : \n");
				preorderTraversal(tree);
				break;
			case 3:
				printf("\n The elements of the tree are : \n");
				inorderTraversal(tree);
				break;
			case 4:
				printf("\n The elements of the tree are : \n");
				postorderTraversal(tree);
				break;
			case 5:
				ptr = findSmallestElement(tree);
				printf("\n Smallest element is :%d", ptr -> data);
				break;
			case 6:
				ptr = findLargestElement(tree);
				printf("\n Largest element is : %d", ptr -> data);
				break;
			case 7:
				printf("\n Enter the element to be deleted : ");
				scanf("%d", &val);
				tree = deleteElement(tree, val);
				break;
			case 8:
				printf("\n Total no. of nodes = %d", totalNodes(tree));
				break;
			case 9:
				printf("\n Total no. of external nodes = %d",
				totalExternalNodes(tree));
				break;
			case 10:
				printf("\n Total no. of internal nodes = %d",
				totalInternalNodes(tree));
				break;
			case 11:
				printf("\n The height of the tree = %d",Height(tree));
				break;
			case 12:
				tree = mirrorImage(tree);
				break;
			case 13:
				tree = deleteTree(tree);
				break;
		}
	}while(option!=14);
	getch();
	return 0;
}

void create_tree(struct node *tree)
{
	tree = NULL;
}

struct node *insertElement(struct node *tree, int val)
{
	struct node *ptr, *nodeptr, *parentptr;
	ptr = (struct node*)malloc(sizeof(struct node));
	ptr->data = val;
	ptr->left = NULL;
	ptr->right = NULL;
	if(tree==NULL)
	{
		tree=ptr;
		tree->left=NULL;
		tree->right=NULL;
	}
	else
	{
		parentptr=NULL;
		nodeptr=tree;
		while(nodeptr!=NULL)
		{
			parentptr=nodeptr;
			if(val<nodeptr->data)
				nodeptr=nodeptr->left;
			else
				nodeptr = nodeptr->right;
		}
		if(val<parentptr->data)
			parentptr->left = ptr;
		else
			parentptr->right = ptr;
	}
	return tree;
}

void preorderTraversal(struct node *tree)
{
	if(tree != NULL)
	{
		printf("%d\t", tree->data);
		preorderTraversal(tree->left);
		preorderTraversal(tree->right);
	}
}


void inorderTraversal(struct node *tree)
{
	if(tree != NULL)
	{
		inorderTraversal(tree->left);
		printf("%d\t", tree->data);
		inorderTraversal(tree->right);
	}
}

void postorderTraversal(struct node *tree)
{
	if(tree != NULL)
	{
		postorderTraversal(tree->left);
		postorderTraversal(tree->right);
		printf("%d\t", tree->data);
	}
}

struct node *findSmallestElement(struct node *tree)
	{
	if( (tree == NULL) || (tree->left == NULL))
		return tree;
	else
		return findSmallestElement(tree ->left);
}

struct node *findLargestElement(struct node *tree)
{
	if( (tree == NULL) || (tree->right == NULL))
		return tree;
	else
		return findLargestElement(tree->right);
}

struct node *deleteElement(struct node *tree, int val)
{
	struct node *cur, *parent, *suc, *psuc, *ptr;
	if(tree->left==NULL)
	{
		printf("\n The tree is empty ");
		return(tree);
	}
	parent = tree;
	cur = tree->left;
	while(cur!=NULL && val!= cur->data)
	{
		parent = cur;
		cur = (val<cur->data)? cur->left:cur->right;
	}
	if(cur == NULL)
	{
		printf("\n The value to be deleted is not present in the tree");
		return(tree);
	}
	if(cur->left == NULL)
		ptr = cur->right;
	else if(cur->right == NULL)
		ptr = cur->left;
	else
	{
		// Find the in-order successor and its parent
		psuc = cur;
		cur = cur->left;
		while(suc->left!=NULL)
		{
			psuc = suc;
			suc = suc->left;
		}
		if(cur==psuc)
		{
			// Situation 1
			suc->left = cur->right;
		}
		else
		{
			// Situation 2
			suc->left = cur->left;
			psuc->left = suc->right;
			suc->right = cur->right;
		}
		ptr = suc;
	}
	// Attach ptr to the parent node
	if(parent->left == cur)
		parent->left=ptr;
	else
		parent->right=ptr;
	free(cur);
	return tree;
}

int totalNodes(struct node *tree)
{
	if(tree==NULL)
		return 0;
	else
		return(totalNodes(tree->left) + totalNodes(tree->right) + 1);
}

int totalExternalNodes(struct node *tree)
{
	if(tree==NULL)
		return 0;
	else if((tree->left==NULL) && (tree->right==NULL))
		return 1;
	else
		return (totalExternalNodes(tree->left) +
	totalExternalNodes(tree->right));
}

int totalInternalNodes(struct node *tree)
{
	if( (tree==NULL) || ((tree->left==NULL) && (tree->right==NULL)))
		return 0;
	else
		return (totalInternalNodes(tree->left) + totalInternalNodes(tree->right) + 1);
}

int Height(struct node *tree)
{
	int leftheight, rightheight;
	if(tree==NULL)
		return 0;
	else
	{
		leftheight = Height(tree->left);
		rightheight = Height(tree->right);
		if(leftheight > rightheight)
			return (leftheight + 1);
		else
			return (rightheight + 1);
	}
}

struct node *mirrorImage(struct node *tree)
{
	struct node *ptr;
	if(tree!=NULL)
	{
		mirrorImage(tree->left);
		mirrorImage(tree->right);
		ptr=tree->left;
		ptr->left = ptr->right;
		tree->right = ptr;
	}
}

struct node *deleteTree(struct node *tree)
{
	if(tree!=NULL)
	{
		deleteTree(tree->left);
		deleteTree(tree->right);
		free(tree);
	}
}