/* Binary Search Tree Insert,Search,Display(Preorder,Inorder,Postorder) */

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

typedef struct link
{
struct link *left;
int data;
struct link *right;
}node;

node *tree=NULL;
node *insert(node*,int);
void search(node *,int);
void preorder(node *);
void postorder(node *);
void inorder(node *);

int main()
{
int val,choice;
while(1)
{
printf("\n1: Insert\n2: Search\n3: Preorder\n4: Inorder\n5: Postorder\n6: Exit :\n");
puts("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:puts("Enter number : ");
 scanf("%d",&val);
 tree=insert(tree,val);
 break;
case 2:puts("Enter the number to be search : ");
  scanf("%d",&val);
  search(tree,val);
  break;
case 3:puts("\nPreorder traversing tree \n");
      preorder(tree);
      break;
case 4:puts("\nInoreder traversing tree \n");
      inorder(tree);
      break;
case 5:puts("\nPostorder traversing tree \n");
      postorder(tree);
      break;
case 6:puts("\nEnd");
  //exit(0);
}
}

getch();
return 0;
}

node *insert(node *tree,int val)
{
if(tree==NULL)
{
tree=(node *)malloc(sizeof(node));
tree->data=val;
tree->left=tree->right=NULL;
}
else if(val>tree->data)
tree->right=insert(tree->right,val);
else if(val<tree->data)
tree->left=insert(tree->left,val);
else
printf("\nDuplicate value: program exited ");
// exit(0);
return tree;
}

void search(node *tree,int v)
{
if(tree==NULL)
{
printf("\nSearch Unsuccessfull");
return;
}
else if(v==tree->data)
{
printf("\nSearch successfull\n Number =%d",v);
return;
}
else if(v<tree->data)
{
search(tree->left,v);
}
else
{
search(tree->right,v);
}
}

void inorder(node *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%5d",tree->data);
inorder(tree->right);
}
}

void preorder(node *tree)
{
if(tree!=NULL)
{
printf("%5d",tree->data);
preorder(tree->left);
preorder(tree->right);
}
}

void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%5d",tree->data);
}
}