Binary Search Tree(BST)

Algorithm : Binary Search Tree(BST)

1.Inserting an element in the tree 
 
Bst_insert(root,key)
{
Given the root of the tree and key value which is to be inserted, we have to insert that
value in its proper place.

ptr=root
flag=false

while(ptr$$$$$NULL && flag=0)
 {                         //if already such value exists,
                                     then insertion isn’t possible.
 save=ptr
 if(key=ptr->data)
  flag=true         //if the value is different, 
                                       then the proper place should be found.
 else if(keydata)
  ptr=ptr->lchild
 else
  ptr=ptr->rchild
 }
if(flag=true)
 print("Insertion not possible")
else
 {
 ptr=getnode()         //inserting the key value
                              by making it a node.
 ptr->data=key
 if(keydata)
  save->lchild=ptr
 else
  save->rchild=ptr
 }

}


2.Finding the parent of a element
 
parent(root,key)
{
Given the root of the tree and key value,
 we have to find the parent node of that value and return it.
 
par=NULL
trav=root
while(key≠trav->data)
 {
 par=trav
 if(keydata)
  trav=trav->lchild
 else
  trav=trav->rchild
 }

return par
}


3. Finding the minimum value within a tree

bstmin(root)
{
Given the root of the tree, we have to find the minimum value within the tree.
 
trav=root
while(trav->lchild≠NULL)
 trav=trav->lchild

return trav
}


4.  Finding the inorder successor of an element
 
insucbst(root,ptr)
{
Given the root of the tree and a pointer ‘ptr’, we have to find
the inorder successor of that node.
 
if(ptr->rchild≠NULL)
 s=bstmin(ptr->rchild)
else
 {
 y=parent(root,ptr->data)
 while(y≠NULL && y->rchild=ptr)
  {
  ptr=y
  y=parent(root,y)
  }
 s=y
 }

return s
}


5.  Finding the maximum value within a tree
 
bstmax(root)
{
Given the root of the tree, we have to find the maximum value within the tree.
 
trav=root
while(trav->rchild≠NULL)
 trav=trav->rchild

return trav
}


6.Deleting a specific node
 
deletebst(root, key)
{
Given the root of the tree and a key value,
we have to delete that value and adjust its children. 

r=search(root,key)

if(r≠NULL)
 {
 par=parent(root,key)                //if the selected element has no chilren
 if(r->lchild=NULL && r->rchild=NULL)
  {
if(r->datadata)
   par->lchild=NULL
  else
   par->rchild=NULL

  }

 else if(r->lchild≠NULL && r->rchild≠NULL)
  {                                      //if the selected 
                                                       element has both the children
  s=insucbst(root,r)

  succ=s->data
  deletebst(root,s->data)

  r->data=succ
  }

 else
  {

  if(r->rchild≠NULL)
   s=r->rchild          //else if the selected
                                              element has any one child.
  else if(r->lchild≠NULL)
   s=r->lchild

  if(par->lchild=r)
   par->lchild=s
  else if(par->rchild=r)
   par->rchild=s
  }

 }
else                                          //if the value isn’t
                                                       found at all.
 print("Given value wasn't found..! :(")

}



In this set of algorithms, we have often used a algorithm called getnode().
This algorithm allocates a node structure in the memory and returns its address to
the variable.Apart from that, several other functions like search(), height(),
push(), pop() etc are used in the program. 
They mean the general operations described before.



C Program For Binary Search Tree(BST)

Source Code:

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

struct tree
{
 char data;
 struct tree *lchild;
 struct tree *rchild;
};

struct tree * gettree()
{
 struct tree *t;
 t=(struct tree *)malloc(sizeof(struct tree));
 t->lchild=NULL;
 t->rchild=NULL;
 return t;
}

struct tree * BST_min(struct tree *root)
{
    struct tree *trav;
    trav=root;
    while(trav->lchild!=NULL)
    {
       trav=trav->lchild;
    }
    return trav;
}

struct tree * BST_max(struct tree *root)
{
    struct tree *trav;
    trav=root;
    while(trav->rchild!=NULL)
    {
       trav=trav->rchild;
    }
    return trav;
}

struct tree * BST_search(struct tree *root,char key)
{
   int flag;
   struct tree *ptr;
   ptr=root;
   flag=0;
   while(ptr!=NULL && flag==0)
   {
      if(ptr->data==key)
  flag=1;
      else if(ptr->data>key)
  ptr=ptr->lchild;
      else if(ptr->datarchild;
   }
   return ptr;
}

void BST_insert(struct tree *root,char key)
{
   struct tree *ptr,*t,*save;
   int flag;
   flag=0;
   ptr=root;
   if(root->data=='$')
      root->data=key;
   else
   {
      while(ptr!=NULL && flag==0)
      {
  save=ptr;
  if(key==ptr->data)
     flag=1;
  else if(keydata)
     ptr=ptr->lchild;
  else if(key>ptr->data)
     ptr=ptr->rchild;
      }
   }
   if(flag==1)
      printf("\nInsertion not possible.");
   else
   {
      t=gettree();
      t->data=key;
      if(keydata)
  save->lchild=t;
      else
  save->rchild=t;
   }
}

struct tree * parent(struct tree *root,struct tree *ptr)
{
   struct tree *par,*trav;
   par=NULL;
   trav=root;
   while(ptr->data!=trav->data)
   {
      par=trav;
      if(ptr->datadata)
  trav=trav->lchild;
      else
  trav=trav->rchild;
   }
   return par;
}

struct tree * InsuccBST(struct tree *root,struct tree *ptr)
{
   struct tree *s,*y;
   if(ptr->rchild!=NULL)
      s=BST_min(ptr->rchild);
   else
   {
      y=parent(root,ptr);
      while(y!=NULL && ptr==y->rchild)
      {
  ptr=y;
  y=parent(root,y);
      }
      s=y;
   }
   return s;
}

int count(struct tree *root)
{
   if(root==NULL)
      return 0;
   else
      return count(root->lchild)+count(root->rchild)+1;
}

void inorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  inorder(root->lchild);
  printf("  %c",root->data);
  inorder(root->rchild);
      }
   }
}

void preorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  printf("  %c",root->data);
  preorder(root->lchild);
  preorder(root->rchild);
      }
   }
}

void postorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  postorder(root->lchild);
  postorder(root->rchild);
  printf("  %c",root->data);
      }
   }
}

int height(struct tree *root)
{
 if(root==NULL)
    return 0;
 else
 {
    if(height(root->lchild)>height(root->rchild))
       return height(root->lchild)+1;
    else
       return height(root->rchild)+1;
 }
}

int nodenum(struct tree *root,int opt)
{
   if(opt==1)
   {
      if(root==NULL)
  return 0;
      else
  return count(root->lchild)+1;
   }
   if(opt==2)
   {
      if(root==NULL)
  return 0;
      else
  return count(root->rchild)+1;
   }
}

void BST_delete(struct tree *root,char key)
{
   struct tree *par,*ptr,*s,*c;
   char val;
   ptr=BST_search(root,key);
   if(ptr==NULL)
       printf("\nKey not found.");
   else
   {
      par=parent(root,ptr);
      if(ptr->lchild==NULL && ptr->rchild==NULL)
      {
  if(par->data>ptr->data)
     par->lchild=NULL;
  else
     par->rchild=NULL;
      }
      else if(ptr->lchild!=NULL && ptr->rchild!=NULL)
      {
 s=InsuccBST(root,ptr);
 val=s->data;
 BST_delete(root,val);
 ptr->data=val;
      }
      else
      {
  if(ptr->lchild!=NULL)
     c=ptr->lchild;
  if(ptr->rchild!=NULL)
     c=ptr->rchild;
  if(ptr==par->lchild)
     par->lchild=c;
  if(ptr==par->rchild)
     par->rchild=c;
      }

   }
}

void main()
{
 int ch,h,c,opt,h1,h2,c1,c2;
 char key,item;
 float v;
 struct tree *root,*s,*rt;
 root=gettree();
 root->data='$';
 while(1)
 {
 printf("\n\nBinary Search Tree Operations:");
 printf("\n\t1.Insertion\n\t2.Deletion\n\t3.Traversal\n\t4.Search");
 printf("\n\t5.Height\n\t6.Count node of the tree");
 printf("\n\t7.Each subtree node number\n\t8.Decide which branch is heavier");
 printf("\n\t9.Exit");
 printf("\n\nEnter your choice:");
 fflush(stdin);
 scanf("%d",&ch);
 switch(ch)
 {
     case 1: if(root->data=='$')
      {
        printf("\nEnter value of the root node:");
        fflush(stdin);
        scanf("%c",&key);
      }
      else
      {
        printf("\nEnter key:");
        fflush(stdin);
        scanf("%c",&key);
      }
      BST_insert(root,key);
      break;
     case 2: printf("\nDeletion:");
      if(root->data=='$')
   printf("\nTree not created.");
      else
      {
         printf("\nEnter the Key:");
         fflush(stdin);
         scanf("%c",&key);
         BST_delete(root,key);
      }
      break;
     case 3: printf("\n\n\t1.Inorder\n\t2.Preorder\n\t3.Postorder");
      printf("\nEnter Your choice:");
      scanf("%d",&ch);
      switch(ch)
      {
         case 1: printf("\nInorder traversal:\n");
          inorder(root);
          break;
         case 2: printf("\nPreorder traversal:\n");
          preorder(root);
          break;
         case 3: printf("\nPostorder traversal:\n");
          postorder(root);
          break;
      }
      break;
     case 4: if(root->data=='$')
         printf("\nTree not created.");
      else
      {
         printf("\nEnter the key:");
         fflush(stdin);
         scanf("%c",&key);
         s=BST_search(root,key);
         if(s!=NULL)
     printf("\nKey found");
         else
     printf("\nKey not found.");
      }
      break;
     case 5: if(root->data=='$')
         printf("\nTree not created.");
      else
      {
         h=height(root);
         printf("\nHeight of the binary tree=%d",h);
      }
      break;
     case 6: if(root->data=='$')
         printf("\nTree not created.");
      else
      {
         c=count(root);
         printf("\nTotal node of the binary tree=%d",c);
      }
      break;
     case 7: if(root->data=='$')
         printf("\nTree not created");
      else
      {
         printf("\nNode-number ???   1.Left-subtree 2.Right-subtree");
         printf("\nEnter your choice:");
         scanf("%d",&ch);
         switch(ch)
         {
     case 1: opt=1;
      h1=nodenum(root,opt)-1;
      printf("\nNode-number of Left subtree=%d",h1);
      break;
     case 2: opt=2;
      h2=nodenum(root,opt)-1;
      printf("\nNode-number of Right subtree=%d",h2);
      break;
         }
      }
      break;
     case 8: if(root->data=='$')
         printf("\nTree not created.");
      else if(root->lchild==NULL && root->rchild==NULL && root->data!=-1)
         printf("\nOnly the root node is present.");
      else
      {
         c1=1;
         h1=nodenum(root,c1)-1;
         c2=2;
         h2=nodenum(root,c2)-1;
         if(h1>h2)
     printf("\nLeft subtree is heavier.");
         else if(h1<h2)
     printf("\nRight subtree is heavier.");
         else
     printf("\nLeft subtree and Right subtree is of same weight.");
      }
      break;
     case 9: exit(0);
 }
 }
}

***************Anothor Approach Of BST*****************

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

struct tree
{
   struct tree *left;
   int info;
   struct tree *right;

};

void insert(struct tree **ptr,int item)

{

   if(*ptr==NULL)

   {

     *ptr=(struct tree *)malloc(sizeof(struct tree));

     (*ptr)->left=(*ptr)->right=NULL;

     (*ptr)->info=item;

     return;

   }

   else

   {

     if(item<(*ptr)->info)

     {

        insert(&((*ptr)->left),item);

     }

     else

     {

        insert(&((*ptr)->right),item);

     }

     return;

   }

}

void delete_tree(struct tree **ptr,int item)

{

   struct tree *move,*back,*temp;

   if(*ptr==NULL)

   {

     printf("Empty tree\n");

     return;

   }

   else

   {

     move=*ptr;

     back=move;

     while(move->info!=item)

     {

        back=move;

        if(iteminfo)

        {

          move=move->left;

        }

        else

        {

          move=move->right;

        }

     }

     if(move->left!=NULL&&move->right!=NULL)

     {

        temp=move->right;

        while(temp->left!=NULL)

        {

          back=temp;

          temp=temp->left;

        }

        move->info=temp->info;

        move=temp;

     }

     if(move->left==NULL&&move->right==NULL)

     {

        if(back->right==move)

        {

          back->right=NULL;

        }

        else

        {

          back->left=NULL;

        }

        free(move);

        return;

     }

     if(move->left==NULL&&move->right!=NULL)

     {

        if(back->left==move)

        {

          back->left=move->right;

        }

        else

        {

          back->right=move->right;

        }

        free(move);

        return;

     }

     if(move->left!=NULL&&move->right==NULL)

     {

        if(back->left==move)

        {

          back->left=move->left;

        }

        else

        {

          back->right=move->left;

        }

        free(move);

        return;

     }

   }

}

void preorder(struct tree *ptr)

{

   struct tree *move;

   move=ptr;

   if(move!=NULL)

   {

     printf(" %d ",move->info);

     preorder(move->left);

     preorder(move->right);

   }

   else

     return;

}

void inorder(struct tree *ptr)

{

   struct tree *move;

   move=ptr;

   if(move!=NULL)

   {

     inorder(move->left);

     printf(" %d ",move->info);

     inorder(move->right);

   }

   else

   return;

}

void postorder(struct tree *ptr)

{

   struct tree *move;

   move=ptr;

   if(move!=NULL)

   {

     postorder(move->left);

     postorder(move->right);

     printf(" %d ",move->info);

   }

   else

     return;

}

int main()

{

   struct tree *root=NULL;

   int item,ch,order;

   char choice,ch1,c;

     do

   {

     printf("\n*******MENU********\n");

     printf("1.Insert.\n");

     printf("2.Delete.\n");

     printf("3.Traversal.\n");

     printf("4.Exit.\n");

     printf("Enter your choice(1-4): ");

     scanf("%d",&ch);

     switch(ch)

      {

        case 1: printf("Enter the element to be inserted:");

          scanf("%d",&item);

          insert(&root,item);

          break;

        case 2: printf("Enter the element to be deleted:");

          scanf("%d",&item);

          delete_tree(&root,item);

          break;

        case 3: printf("a.Preorder.\n");

          printf("b.inorder.\n");

          printf("c.Postorder.\n");

          printf("\nEnter your choice:");

          ch1=getch();

          printf("\nTree:  ");


          switch(ch1)

          {

      case 'a': preorder(root);

           break;

      case 'b': inorder(root);

           break;

      case 'c': postorder(root);

           break;

          }

          break;

        case 4: exit(0);
     break;
        default: printf("wrong choice");

     }

     printf("\ndo you wish to continue?(0/1):");
     scanf("%d",&c);

   }while(c==1);
 getch();
 return 0;
}



output:


*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:20

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:5

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:30

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 15
wrong choice
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:27

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:2

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 1
Enter the element to be inserted:10

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   20  5  2  10  30  27
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   2  5  10  20  27  30
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   2  10  5  27  30  20
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 2
Enter the element to be deleted:20

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   2  5  10  27  30
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 2
Enter the element to be deleted:2

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   5  10  27  30
do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 2
Enter the element to be deleted:27

do you wish to continue?(0/1):1

*******MENU********
1.Insert.
2.Delete.
3.Traversal.
4.Exit.
Enter your choice(1-4): 3
a.Preorder.
b.inorder.
c.Postorder.

Enter your choice:
Tree:   10  5  30
do you wish to continue?(0/1):0