A binary search tree (BST), also known
as an ordered binary tree, is a node-based data structure in which each node
has no more than two child nodes. Each child must either be a leaf node or the
root of another binary search tree. The left sub-tree contains only nodes with
keys less than the parent node; the right sub-tree contains only nodes with
keys greater than the parent node.
Example: Insert 20
into the Binary Search Tree. Tree is not available. So create root node and
place 20 into it.
20
Insert 23 into the given Binary Search
Tree. Since 23 > 20, then 23 will be inserted in the right sub-tree of 20.
20
\
23
Insert 13 into the given Binary Search
Tree. Since 13 < 20, then 13 will be
inserted in left sub-tree of 20.
20
/ \
13 23
Insert 9 into the given Binary Search
Tree.
20
/ \
13 23
/
9
Inserting 14:
20
/ \
13 23
/ \
9 14
Inserting 19:
20
/ \
13 23
/ \
9 14
\
19
Inserting 21:
20
/ \
13 23
/ \ /
9 14 21
\
19
Inserting 27:
20
/ \
13 23
/ \ /
\
9 14 21 27
\
19
Inserting 24:
20
/ \
13 23
/ \ /
\
9 14 21 27
\ /
19 24
Deletion
in Binary Search Tree: There are three different cases that needs to be
considered for deleting a node from binary search tree.
case 1: Node with no children (or)
leaf node
case 2: Node with one child
case 3: Node with two children.
20
/ \
13 23
/ \ /
\
9 14
21 27
\ /
19 24
Case 1: Delete a leaf node/ node with
no children.
20
/ \
13 23
/ \ /
\
9 14 21 27
\ /
19 24
Delete 24 from the above binary search
tree.
20
/ \
13 23
/ \ /
\
9 14 21 27
\
19
Case 2: Delete a node with one child.
20
/ \
13 23
/ \ /
\
9 14 21 27
\ /
19 24
Delete 14 from above binary search
tree.
20
/ \
13 23
/ \ /
\
9 19 21 27
/
24
Case 3: Delete a node with two
children.
Delete a node whose right child is the
smallest node in the right sub-tree. (14 is the smallest node present in the
right sub-tree of 13).
20
/ \
13 23
/ \ /
\
9 14 21 27
\ /
19 24
Delete 13 from the above binary tree. Find
the smallest in the left sub-tree of 13, so replace 13 with 14.
20
/ \
14 23
/ \ /
\
9 19
21 27
/
24
Delete 20 from the below binary search
tree.
20
/ \
13 23
/ \ /
\
9 14 21 27
\
22
Find the smallest node in the right
sub-tree of 20. And that smallest node is 21, so replace 20 with 21. Since 21
has only one child (22), the pointer currently pointing to 21 is made to point
to 22, so the resultant binary tree
would be:
21
/ \
13 23
/ \ / \
9 14 27
\
22
21
/ \
13 23
/ \
/ \
9 14 22 27
Source code (BST operations) :
#include<stdio.h>
#include<stdlib.h>
struct tree {
int info;
struct tree *left;
struct tree *right;
};
struct tree *insert(struct tree
*,int);
void inorder(struct tree *);
void postorder(struct tree *);
void preorder(struct tree *);
struct tree *delet(struct tree *,int);
struct tree *search(struct tree *);
int main(void) {
struct tree *root;
int choice, item,item_no;
root = NULL;
printf("\n******* BINARY SEARCH
TREE OPERATIONS *******\n\n");
do {
do {
printf("\n\t 1. INSERTION
");
printf("\n\t 2. DELETION ");
printf("\n\t 3. INORDER
TRAVERSAL");
printf("\n\t 4. POSTORDER
TRAVERSAL");
printf("\n\t 5. PREORDER
TRAVERSAL");
printf("\n\t 6. SEARCH AND
REPLACE");
printf("\n\t 7. EXIT ");
printf("\n\n ENTER YOUR CHOICE :
");
scanf(" %d",&choice);
if(choice<1 || choice>7)
printf("\n INVALID CHOICE - TRY
AGAIN \n");
}
while (choice<1 || choice>7);
switch(choice)
{
case 1:
printf("\n ENTER NEW ELEMENT:
");
scanf("%d", &item);
root= insert(root,item);
printf("\n ROOT NODE :
%d\n",root->info);
printf("\n UPDATED BINARY TREE
(INORDER TRAVERSAL): ");
inorder(root);
printf("\n");
break;
case 2:
printf("\n ENTER THE ELEMENT TO
BE DELETED : ");
scanf(" %d",&item_no);
root=delet(root,item_no);
printf("\n ROOT NODE :
%d\n",root->info);
printf("\n UPDATED BINARY TREE
(INORDER TRAVERSAL): ");
inorder(root);
printf("\n");
break;
case 3:
printf("\n INORDER TRAVERSAL OF
BINARY TREE: ");
inorder(root);
printf("\n");
break;
case 4:
printf("\n POSTORDER TRAVERSAL OF
BINARY TREE: ");
postorder(root);
printf("\n");
break;
case 5:
printf("\n PREORDER TRAVERSAL OF
BINARY TREE: ");
preorder(root);
printf("\n");
break;
case 6:
root=search(root);
printf("\n");
break;
default:
printf("\n\t\t\tEND OF PROGRAM
\n");
}}
while(choice !=7);
return(0);
}
struct tree *insert(struct tree *root,
int x)
{
if(!root)
{
root=(struct
tree*)malloc(sizeof(struct tree));
root->info = x;
root->left = NULL;
root->right = NULL;
return(root);
}
if(root->info > x)
root->left =
insert(root->left,x);
else {
if(root->info < x)
root->right =
insert(root->right,x);
}
return(root);
}
void inorder(struct tree *root) {
if(root != NULL) {
inorder(root->left);
printf(" %d",root->info);
inorder(root->right);
}
return;
}
void postorder(struct tree *root) {
if(root != NULL)
{
postorder(root->left);
postorder(root->right);
printf(" %d",root->info);
}
return;
}
void preorder(struct tree *root) {
if(root != NULL)
{
printf(" %d",root->info);
preorder(root->left);
preorder(root->right);
}
return;
}
struct tree *delet(struct tree
*ptr,int x) {
struct tree *p1,*p2;
if(!ptr) {
printf("\n ELEMENT NOT FOUND
\n");
return(ptr);
}
else {
if(ptr->info < x) {
ptr->right =
delet(ptr->right,x);
}
else if (ptr->info >x) {
ptr->left=delet(ptr->left,x);
return ptr;
}
else
{
if(ptr->info == x) {
if(ptr->left == ptr->right) {
free(ptr);
return(NULL);
}
else if(ptr->left==NULL) {
p1=ptr->right;
free(ptr);
return p1;
}
else if(ptr->right==NULL) {
p1=ptr->left;
free(ptr);
return p1;
}
else {
p1=ptr->right;
p2=ptr->right;
while(p1->left != NULL)
p1=p1->left;
p1->left=ptr->left;
free(ptr);
return p2;
}}}}
return(ptr);
}
struct tree *search(struct tree *root)
{
int no,i,ino;
struct tree *ptr;
ptr=root;
printf("\n ENTER THE ELEMENT TO
BE SEARCHED : ");
scanf(" %d",&no);
fflush(stdin);
while(ptr) {
if(no>ptr->info)
ptr=ptr->right;
else if(no<ptr->info)
ptr=ptr->left;
else break;
}
if(ptr) {
printf("\n ELEMENT %d WAS FOUND
",no);
printf("\n\n DO YOU WANT TO
REPLACE IT, PRESS 1 FOR YES : ");
scanf(" %d",&i);
if(i==1) {
printf("\n\n ENTER NEW ELEMENT :
");
scanf(" %d",&ino);
ptr->info=ino;
}
else
printf("\n IT'S OKAY! \n");
}
else
printf("\n ELEMENT %d DOES NOT
EXIST IN THE BINARY TREE \n",no);
return(root);
}