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

typedef struct nodetype
{
	int num;
	struct nodetype *left, *right;
}tree;

tree *makenode(int n)
{
	tree *p;
	p=(tree *)malloc(sizeof(tree));
	p->num=n;
	p->left=NULL;
	p->right=NULL;
	return p;
}

tree *insert_tree(int n, tree *root)
{
	if(root==NULL)
		root=makenode(n);
	else if (n<root->num)
	     root->left=insert_tree(n, root->left);
	else if (n>root->num)
		root->right=insert_tree(n, root->right);
	else
	printf("\nElement already exsists");
	return (root);
}

tree *search(int n, tree *root)
{
	if(root==NULL)
	{
		printf("\nElement not found!");
		return root;
	}
	else if(n==root->num)
	{
		printf("\nElement found!");
		return root;
	}
	else if (n<root->num)
	{
		return (search(n,root->left));
	}
	else
		return (search(n, root->right));
}

void inorder(tree *root)
{
	if(root)
	{
		inorder(root->left);
		printf("%d\t", root->num);
		inorder(root->right);
	}
}

void preorder(tree *root)
{
	if(root);
	{
		printf("%d\t", root->num);
		preorder(root->left);
		preorder(root->right);
	}
}

void postorder(tree *root)
{
	if(root)
	{
		printf("%d\t", root->num);
		postorder(root->left);
		postorder(root->right);
	}
}

void main()
{
	tree *root;
	int i, n, elt, s;
	root=NULL;
	clrscr();
	printf("\nEnter the number of elements: ");
	scanf("%d", &n);
	printf("\nEnter the elements: ");
	for(i=0; i<n; i++)
	{
		scanf("%d", &elt);
		root=insert_tree(elt, root);
	}
	printf("\nInorder: ");
	inorder(root);
	printf("\nPreorder: ");
	preorder(root);
	printf("\nPostorder: ");
	postorder(root);
	printf("\nEnter element to be searched: ");
	scanf("%d", &s);
	root=search(s, root);
	getch();
}