Binary Tree Implementation in C with Tree Traversals

We can implement the binary tree using C so that we can add a node, delete a node, and can perform different tree traversals:

 1. Preorder tree traversal

 2. Inorder tree traversal

 3. Post order tree traversal

/// ..............................................BINARY TREE OPERATIONS AND TREE TRAVERSALS

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

///.................................................................DYNAMIC STRUCTURE FOR BINARY TREE

struct tree
{
     int info;
     struct tree *left_subtree;
     struct tree *right_subtree;
};

///...................................................................GLOBAL FUNCTIONS DECLARATIONS

 struct tree* make_tree();
 struct tree* delete_node(struct tree*,int);
 void insert_node(struct tree *);
 void preorder(struct tree *);
 void inorder(struct tree *);
 void postorder(struct tree *);

///....................................................................MAIN FUNCTION

int main()
{
  struct tree *p_tree,*t;
  int choice,del_item;

  printf("\n\t_____________________________****OPERATIONS ON BINARY TREE AND TREE TRAVERSALS****_____________________________\n\n");
  printf("\n1. INSERTION");
  printf("\n2. dELETION");
  printf("\n3. PRE-ORdER TRAVERSAL");
  printf("\n4. IN-ORdER TRAVERSAL");
  printf("\n5. POST-ORdER TRAVERSAL");
  printf("\n6. EXIT FROM MENU\n");

  p_tree = NULL;
 do
 {

  printf("\n\t\t\t\t\t\tEnter Choice: ");
  scanf("%d",&choice);
  switch(choice)
  {
  case 1: ///.........................................................INSERTION
     if(p_tree == NULL)
          p_tree = make_tree();

    else
          insert_node(p_tree);
     break;

  case 2: ///..................................................... ..DELETION
     if(p_tree == NULL)
           printf("Binary Tree Empty.......");
     else
     {
         printf("Enter info to delete:");
         scanf("%d",&del_item);
      if(p_tree->left_subtree == NULL && p_tree->right_subtree == NULL && p_tree->info == del_item)
     {
        t = p_tree;
        p_tree = NULL;
        free(t);
      }
      else
        p_tree = delete_node(p_tree,del_item);
     }
      break;

  case 3:/// ......................................................PRE-ORdER TRAVERSAL

        printf("\n\n\tPRE-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        preorder(p_tree);
     break;
  case 4:///..................................................... IN-ORdER TRAVERSAL

        printf("\n\n\tIN-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        inorder(p_tree);
     break;
  case 5:///...................................................... POST-ORdER TRAVERSAL

        printf("\n\n\tPOST-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        postorder(p_tree);
     break;
  case 6: ///...................................................... TO EXIT

       exit(0);
  default:///........................................................dEFAULT CASE

       printf("\n\tPlease,Enter the choice lying among 1 to 4 .\n");
  }

 }while(1);

 getch();
 return 0;
}

struct tree* make_tree() ///..................................ALLOCATES A NOdE & SETS IT AS A ROOT OF THE TREE
{
    struct tree * p_tree;
    p_tree =(struct tree*)malloc(sizeof(struct tree));
    printf("\n\t\tEnter info: ");
    scanf("%d",&p_tree->info);
    p_tree->left_subtree = NULL;
    p_tree->right_subtree = NULL;
    return p_tree;
}

void insert_node(struct tree *p_tree) ///.............................ALLOWS INSERTION OF A NOdE
{
    struct tree *t,*n;
    t = p_tree;
    n =(struct tree *)malloc(sizeof(struct tree));
    printf("\n\t\tEnter info: ");
    scanf("%d",&n->info);
    n->left_subtree = NULL;
    n->right_subtree = NULL;
 while(t->left_subtree != NULL || t->right_subtree != NULL)
 {
     if(t->left_subtree != NULL)
       if(n->info < t->info)
         t = t->left_subtree;
    if(t->right_subtree != NULL)
       if(n->info>= t->info)
         t = t->right_subtree;
    if((t->left_subtree == NULL) && (n->info < t->info) && (n->info <t->right_subtree->info))
         break;
    if((t->right_subtree == NULL) && (n->info >= t->info) && (n->info >t->left_subtree->info))
         break;
 }
    if((n->info < t->info) && (t->left_subtree == NULL))
         t->left_subtree=n;
    if((n->info > t->info) && (t->right_subtree == NULL))
         t->right_subtree = n;
}

void inorder(struct tree * p_tree)  ///..................................................ALLOWS IN-ORDER TRAVERSAL
{
    //printf("\n\t\t");
    if(p_tree != NULL)
  {
     inorder(p_tree->left_subtree);
     printf("%d    ",p_tree->info);
     inorder(p_tree->right_subtree);
 }
}
void preorder(struct tree *p_tree)  ///..................................................ALLOWS PRE-ORDER TRAVERSAL
{
      //printf("\n\t\t");
    if(p_tree != NULL)
    {
        printf("%d   ",p_tree->info);
        preorder(p_tree->left_subtree);
        preorder(p_tree->right_subtree);
    }
}
void postorder(struct tree *p_tree)  ///.................................................ALLOWS POST - ORDER TRAVERSAL
{
    //printf("\n\t\t");
    if(p_tree != NULL)
    {
        postorder(p_tree->left_subtree);
        postorder(p_tree->right_subtree);
        printf("%d    ",p_tree->info);
    }
}

struct tree * delete_node(struct tree *p_tree,int d)  ///................................ALLOWS DELETION OF A NODE
{
     int f = 0,f1 = 0;
     struct tree *p,*t,*t1,*x;
     t = p_tree;

     //to search found or not
   while(t != NULL)
  {
     if(t->info == d)
    {
      f = 1;
      x = t;
       break;
    }
   if(t->info > d)
   {
     p = t;
     t = t->left_subtree;
   }
   else if(t->info <= d)
  {
     p = t;
     t = t->right_subtree;
   }
   }
   if(f == 0)
   {
    printf("\nThe entered  element not found.......\n");
    return p_tree;
  }

   ///........................................................................if the node to be deleted has no sub-tree
if(x->left_subtree == NULL && x->right_subtree == NULL)
   {
     if(p->right_subtree == x)
         p->right_subtree = NULL;
     else
         p->left_subtree = NULL;
     free(x);
     return p_tree;
   }

    ///......................................................................if the node to be deleted  has left & right sub-trees

if(x->left_subtree != NULL && x->right_subtree != NULL)
   {
      p = x;
      t1 = x->right_subtree;
   while(t1->left_subtree != NULL)
   {
      p = t1; f1 = 1;
      t1 = t1->left_subtree;
   }
    if(t1->left_subtree == NULL && t1->right_subtree == NULL)
    {
       x->info = t1->info;
       if(f1 == 1)
          p->left_subtree = t1->left_subtree;
       if(f1 == 0)
          x->right_subtree = t1->right_subtree;
       free(t1);
       return p_tree;
     }
   if(t1->right_subtree != NULL)
   {
       x->info = t1->info;
      if(f1 == 1)
          p->left_subtree = t1->right_subtree;
      if(f1 == 0)
          p->right_subtree = t1->right_subtree;
      free(t1);
      return p_tree;
    }
   }

     ///..........................................................................if the node to be deleted has oniy right sub-tree

if(x->left_subtree == NULL && x->right_subtree != NULL && x->info!= p_tree->info)
   {
   if(p->left_subtree == x)
       p->left_subtree = x->right_subtree;
   else
       p->right_subtree = x->right_subtree;
    free(x);
    return p_tree;
   }

        ///........................................................................if the node to be deleted has oniy left sub-tree

if(x->left_subtree != NULL && x->right_subtree == NULL && x->info != p_tree->info)
   {
        if(p->left_subtree == x)
              p->left_subtree = x->left_subtree;
        else
              p->right_subtree = x->left_subtree;
        free(x);
        return p_tree;
    }
        if(x->left_subtree != NULL && x->right_subtree == NULL && x->info == p_tree->info)
       {
              p_tree = x->left_subtree;
              free(p);
              return p_tree;
         }
        if(x->left_subtree == NULL && x->right_subtree != NULL && x->info == p_tree->info)
       {
           p_tree = x->right_subtree;
           free(p);
           return p_tree;
        }
}