/*12.PROGRAM ON BINARY SEARCH TREE*/
#include<stdio.h>
#include<conio.h>
#include<process.h>
struct node
   {
    int info;
    struct node *llink;
    struct node *rlink;
    };
typedef struct node *NODE;
NODE getnode()
   {
    NODE x;
    x=(NODE)malloc(sizeof(struct node));
    if(x==NULL)
     {
      printf("\nOut of memory\n");
      exit(0);
     }
    return x;
   }
NODE insertion(int item,NODE root)
    {
     NODE temp,prev,cur;
     temp=getnode();
     temp->info=item;
     temp->llink=NULL;
     temp->rlink=NULL;
     if(root==NULL)
      return temp;
     prev=NULL;
     cur=root;
     while(cur!=NULL)
	{
	 prev=cur;
	 if(item==cur->info)
	  {
	   printf("NO Duplicate nodes are allowed\n");
	   return root;
	  }
	 if(item<cur->info)
	  cur=cur->llink;
	 else
	  cur=cur->rlink;
	}
       if(item<prev->info)
	prev->llink=temp;
       else
	prev->rlink=temp;
     return root;
   }
void preorder(NODE root)
   {
    if(root!=NULL)
     {
      printf("%d\t",root->info);
      preorder(root->llink);
      preorder(root->rlink);
     }
   }

void inorder(NODE root)
    {
     if(root!=NULL)
       {
	inorder(root->llink);
	printf("%d\t",root->info);
	inorder(root->rlink);
       }
    }

void postorder(NODE root)
   {
    if(root!=NULL)
     {
      postorder(root->llink);
      postorder(root->rlink);
      printf("%d\t",root->info);
     }
   }
void main()
   {
    NODE root=NULL;
    int item,ch;
    for(;;)
      {
       clrscr();
       printf("\n1: INSERT\n2: PREORDER\n3: INORDER\n4: POSTORDER\n5. EXIT\n");
       printf("\nEnter ur choice : ");
       scanf("%d",&ch);
	switch(ch)
	      {
		case 1:
		      printf("Enter the item to insert\n");
		      scanf("%d",&item);
		      root=insertion(item,root);
		      break;
		case 2:
		      if(root==NULL)
			printf("Tree is empty\n");
		      else
		       {
			printf("\nPreorder Traversal\n");
			preorder(root);
		       }
			break;
		case 3:
		       if(root==NULL)
			printf("Tree is empty\n");
		       else
			{
			 printf("\nInorder Traversal\n");
			 inorder(root);
			}
			break;
		case 4:
		       if(root==NULL)
			printf("Tree is empty\n");
		       else
			{
			 printf("\nPostorder Traversal\n");
			 postorder(root);
			}
			 break;
		case 5:
		      exit(0);
		default:
		     printf("Invalid inputs");

		}
		getch();
	}
 }