/*Program for traversal of BST*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct nodetype { int info; struct nodetype *left, *right; }*p,*q;
typedef struct nodetype *  NODE;
NODE maketree(int x)
{
 p=(NODE)malloc(sizeof(struct nodetype));
 p->info=x;
 p->left=p->right=NULL;
 return(p);
}
void setleft(NODE p, int x)
{
 if(p==NULL)  printf("\nVoid insertion");
 else if(p->left!=NULL)
 printf("\nInvalid insertion");
 else p->left=maketree(x);
}
void setright(NODE p,int x)
{
 if(p==NULL)  printf("\nVoid Insertion");
 else if(p->right!=NULL)
 printf("\nInvalid insertion");
 else
 p->right=maketree(x);
}
void inorder(NODE x)
{
 if(x!=NULL)
 {
  inorder(x->left);
  printf("d  ", x->info);
  inorder(x->right);
 }
}
int del(struct nodetype *ptree, int x)
{
 struct nodetype *p,*q, *f, *rp, *s;
 p=ptree; q=NULL;
 while((p!=NULL) &&(p->info!=x))
 {
  q=p;
  p=(x<p->info)?p->left:p->right;
 }
 if(p==NULL){ printf("\nElement doesn't exist"); return(0);}
 if(p->left==NULL)rp=p->right;  //for removing node//
 else if(p->right==NULL) rp=p->left;
 else  //when node to be removed has both left and right children//
 {
  f=p; rp=p->right; s=rp->left;
  while(s!=NULL)
  { f=rp;  rp=s;  s=rp->left; }
  if(f!=p)  { f->left=rp->right; rp->right=p->right; }
  rp->left=p->left;
 }
 if(q==NULL) ptree=rp;
 else if(p==q->left) q->left=rp;
 else q->right=rp;
 free(p);
}

void main()
{
 int num,data; NODE ptree;
 char ch,Y,N;
 clrscr();
 printf("Enter data randomly and terminate by giving 0:");
 scanf("%d", &num);
 ptree=maketree(num);
 scanf("%d", & data);
 while(data!=0)
 {
  p=q=ptree; num=data;
  while((num!=p->info)&&(q!=NULL))
  {
   p=q;
   if(num>p->info)  q=p->right;
   else  q=p->left;
  }
   if(num==p->info)  printf("\nDuplicate number");
   else if(num>p->info)
   setright(p,num);
   else setleft(p,num);
   scanf("%d", &data);
  }
  printf("\nInorder traversal is as follows:\n");
  inorder(ptree);
  getch();
  printf("Do you want to delete a data? Y/N");
  getc(ch);
  if(ch==Y)
  printf("The deleted number is %d", del(*ptree, x));
  getch();
 }