Binary Search Tree

Binary Search Tree : Binary search tree is a tree in which the left descendant has data lower than the node and the right descendant has data greater than the node. A binary search tree has several applications. It can be used to detect duplicates, sort a list, efficient search and delete the items. The inorder traversal of a binary search tree prints the elements in increasing order.

C program implementing binary search tree.

//Binary Search Tree
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

typedef struct node
{
 int data;
 struct node*left;
 struct node*right;
}node;

//insert node in a binary search tree
void insert(node**bst,int n)
{ 
 
 if(*bst==NULL)//if node is NULL than create a node
 {
  *bst=(node*)malloc(sizeof(node));
  (*bst)->data=n;
  (*bst)->left=NULL;
  (*bst)->right=NULL;
 }
 else
 { //if number is less than node data than insert in left subtree
  if(n<(*bst)->data)
  insert(&((*bst)->left),n);
  else//insert in right subtree
  insert(&((*bst)->right),n);
 }
}

//search for a parent node and node to be deleted
void search(node**bst,node**par,node**del,int*found,int n)
{ node*temp=*bst;
 if(temp==NULL)
 {
  *found=0;
  return;
 }
 *par=NULL;
 while(temp!=NULL)
 {
  if(temp->data==n)
  {
   *del=temp;
   *found=1;
   return;
  }
  *par=temp;
  if(n<temp->data)
  temp=temp->left;
  else
  temp=temp->right;
  
 }
 
}

//delete a node and adjust the binary search tree
void delete(node**bst,int n)
{ node*par=NULL,*del=NULL,*par1=NULL,*del1=NULL,*temp=NULL;
 int flag=0;
 
 //Tree is empty
 if(*bst==NULL)
 {
  printf("\nTree is empty!!!");
  return;
 }
 
 //search for parent node and node to be deleted
 search(bst,&par,&del,&flag,n);
 
 //if node is not present
 if(flag==0)
 {
  printf("\n Data not found");
  return;
 }
 
 //if node found
 
 //if left and right subtree of the concerned node is not empty
 if(del->left!=NULL && del->right!=NULL)
 { 
  
  //find inorder successor
  del1=del->right;
  while(del1->left!=NULL)
  {
   par1=del1;
   del1=del1->left;
  }
  
  
  par1->left=del1->right;//set left link of parent of inorder successor to child of successor
  del1->left=del->left;//set left link of successor to the left descendant of to be deleted node
  del1->right=del->right;//set right link of successor to the right descendant of to be deleted node
  //delete the concerned node
  if(par->data>del->data) 
  par->left=del1;
  else
  par->right=del1;
  free(del);
  return;
 }
 
 if(del->left==NULL && del->right==NULL)
 {
  if(del->data>par->data)
  par->right=NULL;
  else
  par->left=NULL;
  free(del);
  return;
 }
 
 if(del->right!=NULL)
 {
  if(del->data>par->data)
  par->right=del->right;
  else
  par->left=del->right;
  free(del);
  return;
 }
 if(del->left!=NULL)
 {
  if(del->data>par->data)
  par->right=del->left;
  else
  par->left=del->left;
  free(del);
  return;
 }
 
}

//traverse the tree in inorder
void inorder(node*bt)
{
 if(bt!=NULL)
 {
  inorder(bt->left);
  printf("%d\t",bt->data);
  inorder(bt->right);
 }
}

//traverse the tree in preorder
void preorder(node*bt)
{
 if(bt!=NULL)
 {
  printf("%d\t",bt->data);
  preorder(bt->left);
  preorder(bt->right);
 }
}

//traverse the tree in postorder
void postorder(node*bt)
{
 if(bt!=NULL)
 {
  postorder(bt->left);
  postorder(bt->right);
  printf("%d\t",bt->data);
  
 }
}


void main()
{
 node*bst=NULL;
 insert(&bst,6);
 insert(&bst,2);
 insert(&bst,1);
 insert(&bst,5);
 insert(&bst,3);
 insert(&bst,4);
 insert(&bst,9);
 insert(&bst,7);
 insert(&bst,10);
 inorder(bst);
 printf("\n");
 preorder(bst);
 delete(&bst,2);
 printf("\n");
 postorder(bst);
 
}