C Program for Binary Search Tree

C Program for Binary Search Tree

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node  *lchild;
 struct node *rchild;
 
};
void ins_bst(struct node**,int);
void del_bst(struct node **,int);
void pre_bst(struct node *);
 void in_bst(struct  node*);
void post_bst(struct node*);
struct node *inos(struct node *);
main()
{
 int i,ch;
 struct node *root=NULL;
 while(1)
 {
  printf("*********\n\tMENU\n********");
  printf("\n1.Insertion\n2.Deletion\nTRAVERSAL\n3.Inorder\n4.Preorder\n5.Postorder\n6.Exit\nEnter ur choice\n");
 scanf("%d",&ch);
 switch(ch)
 {
  case 1:
   printf("Enter the data\n");
   scanf("%d",&i);
   ins_bst(&root,i);
   break;
  case 2:
   printf("Enter the item to be deleted\n");
   scanf("%d",&i);
   del_bst(&root,i);
   break;
  case 3:
   printf("THE INORDER TRAVERSAL\t");
   in_bst(root);
   printf("\n");
   break;
  case 4:
   printf("THE PREORDER TRAVERSAL\t");
   pre_bst(root);
   printf("\n");
   break;
  case 5:
   printf("THE POSTORDER TRAVERSAL\t");
   post_bst(root);
   break;
  case 6:
   exit(0);
   break;
  default:
   printf("SORRY WRONG CHOICE\n");

 }
}
}
void in_bst(struct node *root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)
 {
  in_bst(ptr->lchild);
  printf("%d\t",ptr->data);
  in_bst(ptr->rchild);
 }
}
void ins_bst(struct node **root,int item)
{
 int f=0;
 struct node *ptr,*temp,*parent;
 ptr=*root;
 parent=*root;
 while(ptr!=NULL&&f==0)
 {
  if(item==ptr->data)
  {
   printf("ITEM ALREADY EXISTS\n");
   f=1;
  }
  else if(item>ptr->data)
  {
   parent=ptr;
   ptr=ptr->rchild;
  }
  else if(item<ptr->data)
  { parent=ptr;
   ptr=ptr->lchild;
  }
 }
 if (f==0)
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if(temp==NULL)
  {
   printf("The node is not created\n");
  }
  else
  {
   temp->data=item;
   temp->rchild=NULL;
   temp->lchild=NULL;
   if(*root==NULL)  
   {
    *root=temp;
   }
   else
   {
    if(item>parent->data)
     parent->rchild=temp;
    else
    {
     parent->lchild=temp;
    }
   }
  }
 }
}
void del_bst(struct node **root,int item)
{
 int f=0,c,i1;
 struct node *ptr1,*ptr,*parent;
 ptr=*root;
 parent=*root;
 while(ptr!=NULL&&f==0)
 {
  if(ptr->data==item)
   f=1;
  else if (item>ptr->data)
  {
   parent=ptr; 
   ptr=ptr->rchild;
  }
  else /* if(item<ptr->data)*/
  {
   parent=ptr;
   ptr=ptr->lchild;
  }
 }
 if(f==0)
 {
  printf("Item is not present\n");
  /* return(0);*/
 }
 else
 {
  if(ptr->lchild==NULL&&ptr->rchild==NULL)
  {
   c=0;
  }
  else if (ptr->lchild!=NULL && ptr->rchild!=NULL)
  {
   c=2;
  }
  else
  {
   c=1;
  }

  if(c==0)
  {
   if(parent==ptr) 
    *root=NULL;
   else
   {

    if(parent->lchild==ptr)
    { 
     parent->lchild=NULL;
    }
    else
    {
     parent->rchild=NULL;
    }
    free(ptr);
   }
  }
  if(c==1)
  {
   if(parent==ptr)
   {
    if(parent->rchild==NULL)
    {
     *root=parent->lchild;
    }
    else
    {
     *root=parent->rchild;
    }
   }
   else if(parent->lchild==ptr)
   {
    if(ptr->lchild==NULL)
    {
     parent->lchild=ptr->rchild;
    }
    else
    {
     parent->lchild=ptr->lchild;
    }
   }  
   else
   {
    if(ptr->lchild==NULL)
    {
     parent->rchild=ptr->rchild;
    }
    else
    {

     parent->rchild=ptr->lchild;
    }
   }
   free(ptr);
  }
  if(c==2)
  {
   ptr1=inos(ptr);
   i1=ptr1->data;
   del_bst(root,i1);
   ptr->data=i1;
  }
 
 }
}
struct node*inos(struct node *ptr)

{
 ptr=ptr->rchild;
 if(ptr!=NULL)
 {
  while(ptr->lchild!=NULL)
  {
   ptr=ptr->lchild;
  }
 }
 return(ptr);
}
void pre_bst(struct node *root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)
 {
  printf("%d\t",ptr->data);
  pre_bst(ptr->lchild);
  pre_bst(ptr->rchild);
 }
 
 
}
void post_bst(struct node*root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)

 {
  post_bst(ptr->lchild);
  post_bst(ptr->rchild);
  printf("%d\t",ptr->data);
 }

}

Output