Programming Geek
Rated 4.1/5 based on 446 reviews

### 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)
{
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);

}

```