IMPLEMENTATION OF BINARY SEARCH TREE
PROGRAM
#include<stdio.h>
#include<stdlib.h>
typedef struct bst
{
int data;
struct bst*left,*right;
}node;
void insert(node*,node*);
void inorder(node*);
node*search(node*,int,node**);
void del(node*,int);
void main()
{
int choice;
char ans='N';
int key;
node*new,*root,*temp,*parent;
node*getnode();
root=NULL;
printf("\n\tprogram for binary search tree");
do
{
printf("\n1.create\n2.search\n3,delete\n4.display");
printf("\nenter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:do
{
new=getnode();
printf("\nenter the element");
scanf("%d",&new->data);
if(root==NULL)
root=new;
else
insert(root,new);
printf("\ndo u wish to enter more elements?(y/n)");
}while(ans=='y');
break;
case 2:
printf("\nenter the element which you want to search");
scanf("%d",&key);
temp=search(root,key,&parent);
printf("\nparent of node %dis%d",temp->data,parent->data);
break;
case 3:
printf("\nenter the element u wish to delete");
scanf("%d",&key);
del(root,key);
break;
case 4:
if(root==NULL)
printf("tree is not created");
else
{
printf("\nthe tree is");
inorder(root);
}
break;
}
}while(choice!=5);
}
node*getnode()
{
node*temp;
temp=(node*)malloc(sizeof(node));
temp->left=NULL;
temp->right=NULL;
return temp;
}
void insert(node*root,node*new)
{
if(new->data<root->data)
{
if(root->left==NULL)
root->left=new;
else
insert(root->left,new);
}
if(new->data>root->data)
{
if(root->right==NULL)
root->right=new;
else
insert(root->right,new);
}
}
node*search(node*root,int key,node**parent)
{
node*temp;
temp=root;
while(temp!=NULL)
{
if(temp->data==key)
{
printf("\nthe %d element is parent",temp->data);
return temp;
}
*parent=temp;
if(temp->data>key)
temp=temp->left;
else
temp=temp->right;
}
return NULL;
}
void del(node*root,int key)
{
node*temp,*parent,*tempsucc;
temp=search(root,key,&parent);
if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
tempsucc=temp->right;
while(tempsucc->left!=NULL)
{
parent=tempsucc;
tempsucc=tempsucc->left;
}
temp->data=tempsucc->data;
parent->right=NULL;
printf("now deleted it!");
return;
}
if(temp->left!=NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
free(temp);
printf("now deleted it!");
return;
}
if(temp->left==NULL&&temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=temp->right;
temp=NULL;
free(temp);
printf("now deleted it!");
return;
}
if(temp->left==NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
printf("now deleted it!");
return;
}
}
void inorder(node*temp)
{
if(temp!=NULL)
{
inorder(temp->left);
printf("%d",temp->data);
inorder(temp->right);
}
}
OUTPUT
program for binary search tree
1.create
2.search
3,delete
4.display
enter your choice1
enter the element10
do u wish to enter more elements?(y/n)
1.create
2.search
3,delete
4.display
enter your choice1
enter the element20
do u wish to enter more elements?(y/n)
1.create
2.search
3,delete
4.display
enter your choice1
enter the element30
do u wish to enter more elements?(y/n)
1.create
2.search
3,delete
4.display
enter your choice1
enter the element40
do u wish to enter more elements?(y/n)
1.create
2.search
3,delete
4.display
enter your choice4
the tree is10203040
1.create
2.search
3,delete
4.display
enter your choice3
enter the element u wish to delete30
the 30 element is parentnow deleted it!
1.create
2.search
3,delete
4.display
enter your choice2
enter the element which you want to search20
the 20 element is parent
parent of node 20is10
1.create
2.search
3,delete
4.display
