#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
 
void formatting(void);
int input(void);
struct binTree* createNode(struct binTree*,int);
void insert(struct binTree*, int);
struct binTree* searchNode(struct binTree*, int);
struct binTree* search(struct binTree*, int);
void dispTree(struct binTree*);
 
	struct binTree{
			int item;
			struct binTree *leftChild, *rightChild;
			}*root=NULL, *node;
 
void main(void)
{
	char choice;
	int data;
	struct binTree* newNode;
	clrscr();
	formatting();
	do{
		fflush(stdin);
		printf("\n\n[E]nter, [S]earch a number or [Q]uit: ");
		choice = getche();
		switch(choice)
		{
			case 'E':
			case 'e':
				data = input();
				newNode = createNode(newNode, data);
				insert(newNode, data);
				break;
 
			case 'S':
			case 's':
				data = input();
				newNode = search(root, data);
 
				if(newNode == NULL) printf("\nItem not found");
				else printf("Item = %d found @add %p", data, newNode);
				break;
 
 
			case 'Q':
			case 'q':
				exit(1);
 
			default:
				printf("\nYou entered different choice");
		}
		dispTree(root);
		}while(choice != 'q');
 
	getch();
}
 
void dispTree(struct binTree* pNode)
{
	static int c = 0;
	int i = 0;
 
	for(i = 0; i< c; i++)
		printf("...");
 
	printf("%d\n", pNode->item);
 
	c++;
	if(pNode->leftChild != NULL)
		dispTree(pNode->leftChild);
 
	if(pNode->rightChild != NULL)
		dispTree(pNode->rightChild);
 
	c--;
}
 
struct binTree* search(struct binTree* pNode, int data)
{
	if(data == pNode->item || pNode == NULL)
		return(pNode);
 
	if(data < pNode->item)
		search(pNode->leftChild, data);
 
	else
		search(pNode->rightChild, data);
}
 
void insert(struct binTree* newNode, int data)
{
	struct binTree* pNode;
	if(root == NULL)
		root = newNode;
 
	else{
		pNode = searchNode(root, data);
		if(data < pNode->item) pNode->leftChild = newNode;
		if(data > pNode->item) pNode->rightChild = newNode;
		}
}
 
struct binTree* searchNode(struct binTree* pNode, int data)
{
	if(data < pNode->item && pNode->leftChild != NULL)
		pNode = searchNode(pNode->leftChild, data);
 
	if(data > pNode->item && pNode->rightChild != NULL)
		pNode = searchNode(pNode->rightChild, data);
 
	return(pNode);
}
 
int input(void)
{
	int data;
	printf("\nEnter the number: ");
	scanf("%d", &data);
	return(data);
}
struct binTree* createNode(struct binTree* newNode, int data)
{
	newNode = (struct binTree*)malloc(sizeof(struct binTree));
	newNode->item = data;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;
 
	return(newNode);
}
 
void formatting(void)
{
	int i;
	printf("\n");
	for(i =0; i<=79 ; i++)
		printf("*");
 
	printf("\n......... Prgogram title\t\t# Binary Tree");
	printf("\n......... Created by\t\t        # Romasa Qasim");
	printf("\n......... Description\t\t 	# Creation of Binary Search Tree\n");
 
	for( i =0; i<=79 ; i++)
		printf("*");
}