C code to implement Binary Search Tree | BST Program

A "binary search tree" or "ordered binary tree" is a type of binary tree in which all nodes of left subtree are less than or equal the parent node and all nodes of right subtree are greater than the parent node.

For example: X is parent node,Y is left node and Z is right node than Y<=X and Z>X.

Binary search tree is used to construct more abstract data structure like sets, multi-sets and associative arrays.

/* C program to implement binary search tree */

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

 struct node
       {
         int data;
         struct node *lc,*rc;
       };

  typedef struct node NODE;

  void create(NODE **,int);
  void inorder(NODE *);
  void searche(NODE * ,int);
  void del(NODE **,int);
  void search(NODE **,int,NODE **,NODE **,int*);

/* main function */

 void main()
     {
       NODE *root=NULL;
       int data;
       char ch;
       clrscr();
       printf("Enter the root element:-   ");
       scanf("%d",&data);
       create(&root,data);
    while(1)
     {
      printf("\n   MENU \n");
      printf("\n1.Insert.");
      printf("\n2.Search.");
      printf("\n3.Delete.");
      printf("\n4.Display.");
      printf("\n5.Exit\n");
      printf("\nEnter your choice:-   ");
      fflush(stdin);
      scanf("%c",&ch);
       switch(ch)
        {
         case '1':
              printf("\nEnter the data :-    ");
              scanf("%d",&data);
              create(&root,data);
              break;
         case '2':
              printf("\nEnter the element to be search:-    ");
              scanf("%d",&data);
              searche(root,data);
              break;
         case '3':
              printf("\nEnter the element to be delete:-    ");
              scanf("%d",&data);
              del(&root,data);
              break;
         case '4':
              printf("\nIn-order Traversal:\n");
              inorder(root);
              break;
         case '5':
              exit(1);
         default:
             printf("\nYou have entered a wrong choice.");
        }
     }
  }

/* create function to construct binary search tree */

void create(NODE **root,int d)
     {

       if(*root==NULL)
      {
        *root=(NODE *)malloc(sizeof(NODE));
        (*root)->data=d;
        (*root)->lc=NULL;
        (*root)->rc=NULL;
        return;
      }
    else
      {
        if( d < (*root)->data )
           create(&((*root)->lc),d);
        if( d > (*root)->data )
           create(&((*root)->rc),d);
        if( d == (*root)->data )
           printf("\nData already exist.");
       }
     }

/* inorder function to print all nodes in order from binary search tree */

void inorder(NODE *root)
      {
    if(root!=NULL)
     {
       inorder(root->lc);
       printf("%4d",root->data);
       inorder(root->rc);
     }
    }

/* searche function to search a specific node in binary search tree */

void searche(NODE *root,int d)
     {
      if(root!=NULL)
       {
         if( d < root->data )
           searche(root->lc,d);
         if( d > root->data )
           searche(root->rc,d);
         if( d == root->data )
           printf("\nData Found");
       }
      else
       printf("\nData not Found");
     }

/* del function to delete a node from binary search tree */

void del(NODE **root,int n)
 {
   int found;
   NODE *parent,*x,*xsucc;

   if(*root==NULL)
      printf("\nTree is empty");
   parent=x=NULL;

   search(root,n,&parent,&x,&found);

   if(found==0)
     printf("\nDATA TO BE DELETED NOT FOUND!!!\n");
   if(x->lc!=NULL && x->rc!=NULL)
     {
    parent=x;
    xsucc=x->rc;

     while(xsucc->lc!=NULL)
       {
         parent=xsucc;
         xsucc=xsucc->lc;
       }
     x->data=xsucc->data;
     x=xsucc;
     }
     if(x->lc==NULL && x->rc==NULL)
    {
       if(parent->rc==x)
           parent->rc=NULL;
       else
           parent->lc=NULL;      
     }
     if(x->lc==NULL && x->rc!=NULL)
     {
        if(parent->lc==x)
           parent->lc=x->rc;
        else
           parent->rc=x->rc;        
     }
     if(x->lc!=NULL && x->rc==NULL)
      {
         if(parent->lc==x)
        parent->lc=x->lc;
         else
        parent->rc=x->lc;        
       }
  }

/* search function that is used in del function to find the availability of any node */

void search(NODE **root,int n,NODE **par,NODE **x,int *found)
  {
     NODE *q;

     q=*root;
     *found=0;
     *par=NULL;

       while(q!=NULL)
       {
        if(q->data==n)
         {
          *found=1;
          *x=q;
          return;
         }
        *par=q;
     if(q->data>n)
      q=q->lc;
     else
      q=q->rc;
       }
  }

/* Output of Binary Search Tree Program */

Output of Binary Search Tree

Output of Binary Search Tree

For more related to Data Structure Programs check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.