Search & Deletion in Binary search Tree ( BST )

In previous discussion we discus about Binary search tree Now we have to do some basic operation on binary search tree.

Searching a element : it is not a tough job in BST .follow simple algorithm

>> compare root node data with require data if equal search complete otherwise if less that root node move to left else move to right child.

follow this steps for all nodes until NULL encounter it is condition for unsuccessful search.

Delete a element : It is slightly tough . first search node position & its parent node. location.than deletion process starts : :

There are four type of cases encounter :

>> node to be delete have no child (i.e leaf node ) = you can delete it directly .just like delete last element of one way link list.

>> node to be delete have one left child . = also simple just like delete first node in One way link list .  

>>  node to be delete have one right child = similar as above.

>> Node to be delete have two child = than find its inorder successor than replace node value by of its inorder successor . than delete that inorder successor.

To read it with more detail Download : Binary search tree complete .

C PRogram :

 // all operation on Binary Search Tree  
 #include<stdio.h>  
 #include<malloc.h>  
 #include<stdlib.h>  
 struct node  
 {  
      struct node *lc;  
      struct node *rc;  
      char data;  
 };  
 typedef struct node node; //typedef  
 void insert(node **,char);  
 void inorder(node *);  
 void preorder(node *);  
 void postorder(node *);  
 void search(node **,node **,node **,char,int *);  
 void del(node **,char);  
 void main()  
 {  
           int i,k;  
        char c;  
      node *root;  
      root=NULL;  
      printf("\n NO of element u wan't to insert :");  
      scanf("%d",&k);  
      getchar();  // use to take enter as input in to buffer to prevent it as input in next char input  
      for(i=0;i<k;i++)  
      {  
           printf("\n insert %dth charactor element :",i+1);  
           scanf("%c",&c);  
           getchar();  
           insert(&root,c);  
      }  
      /*----------------------------operation--------------------------*/  
      while(1)  
      {  
      printf("\n\n\n 1 for deletion :");  
      printf("\n 2 for traversal :");  
      printf("\n any other no to exit\n");  
      printf("\n\n enter ur choice :");  
      scanf("%d",&k);  
      getchar();  
      switch(k)  
      {  
           case 1:  
                printf("\n enter character u wan't to delete : ");  
                 scanf("%c",&c);  
              getchar();  
             del(&root,c);  
             break;  
           case 2:  
                     /*------------------------------------traversal-------------------------------*/  
                          printf("\n inorder traversal :\n");  
                          inorder(root);  
                          printf("\n preorder traversal :\n");  
                          preorder(root);  
                          printf("\n postorder traversal :\n");  
                          postorder(root);  
                     /*-----------------------End of traversal-------------------------------*/  
                  break;  
           default :  
                 exit(0);  
                 break;  
      }  
   }  
      /*---------------------------end of operation--------------------------------*/  
 }// end of main  
 /*------------------------------funtion definations--------------------------*/  
 void insert(node **tr,char c)  
 {  
      if(*tr==NULL) // tree is empty so insert as first node  
      {  
           *tr=(node *)malloc(sizeof(node));  
           (*tr)->data=c;  
           (*tr)->rc=NULL;  
           (*tr)->lc=NULL;  
      }  
      else  
      {  
           if(c <(*tr)->data)  
           {  
                insert(&(*tr)->lc,c);  
           }  
           else  
             insert(&(*tr)->rc,c);  
      }  
 }  
 void inorder(node *tr)  
 {  
      if(tr!=NULL)  
      {  
           inorder(tr->lc);  
           printf(" %c ",tr->data);  
           inorder(tr->rc);  
      }  
 }  
 void preorder(node *tr)  
 {  
      if(tr!=NULL)  
      {  
           printf(" %c ",tr->data);  
           preorder(tr->lc);  
           preorder(tr->rc);  
      }  
 }  
 void postorder(node *tr)  
 {  
      if(tr !=NULL)  
      {  
     postorder(tr->lc);  
           postorder(tr->rc);  
           printf(" %c ",tr->data);            
   }  
 }  
 void del(node **root,char ch)  
 {  
      int found;  
      node *par=NULL,*rnode=NULL,*rnode_succ=NULL; //rnode=requre node(node to be delete)  
      if(*root==NULL)            // rnode_succ=inorder successor of "rnode"  
      {  
           printf("\n list is empty :");  
           return;  
      }  
      /*call search funtion to find node to be delete*/  
      search(root,&par,&rnode,ch,&found);  
      if(found == 0) // requre node not found  
      {  
           printf("\nthis character is not found in list:");  
           return;  
      }  
      /*case A=>if node to be delete have to child */  
      if(rnode->lc!=NULL && rnode->rc!=NULL)  
      {  
           /*now find out inorder succesor of rnode .It replace rnode after deletion*/  
           par=rnode;  
           rnode_succ = rnode->rc;  
           while(rnode_succ->lc != NULL)  
           {  
                par=rnode_succ;  
                rnode_succ=rnode_succ->lc;  
           }//search for inorder succesoso complete  
            rnode->data=rnode_succ->data;// assigning volue of rnode_succ to rnode  
            rnode=rnode_succ;  //confusing point...  
            /* because rnode_succ may have right child.. now we delete  
              rnode_succ .for that  
             we assign new "rnode" & "par" which will deleted according to  
             condition they satisfy in further conditions of deletion !*/  
      }  
      /*case_B_1=if node has to delete has only one child that is right*/  
      if(rnode->lc==NULL && rnode->rc!=NULL)  
      {  
           if(par->lc==rnode)  
             par->lc=rnode->rc;  
           else  
            par->rc=rnode->rc;  
            free(rnode); // free memory space  
            return;  
      }  
      /*case_B_2=if node to deleted have only one child that is right child*/  
      if(rnode->lc!=NULL && rnode->rc==NULL)  
      {  
           if(par->lc==rnode)  
              par->lc=rnode->lc;  
        else  
          par->rc=rnode->rc;  
          free(rnode); // free memory space of node deleted  
          return;  
      }  
      /*case C=> if node to be delete is leaf node i.e have no child*/  
      if(rnode->lc==NULL && rnode->rc==NULL)  
      {  
           if(par->lc==rnode)  
            par->lc=NULL;  
           else  
            par->rc=NULL;  
            free(rnode);// free memory space  
            return;  
      }  
 }  
 void search(node **root,node **par,node **rnode,char ch,int *f)  
 {  
      node *q=NULL;  
       q=*root;  
       *f=0;  
      while(q!=NULL)  
      {   
       /*if node t be deleted is found*/  
        if(q->data == ch)  
        {  
             *f = 1;  
             *rnode=q;  
             //printf(" jhbjdvfv= %d",*f);  
             return;  
        }  
        //printf("data find - %c\n",q->data);  
        *par=q;  
        if(q->data > ch)  
        {  
             q=q->lc;  
        }  
        else  
        q=q->rc;  
   }  
 }  

OUTPUT :