Binary Search Tree Program with Output


Program : 

#include<stdio.h>
#include<conio.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,*tmp,*parent;
node *get_node();
root=NULL;
clrscr();
printf("\n \t Program for Binary Search Tree");
do
{
printf("\n1 Create \n2. Search \n3.Delete \n4.Display\n 5.Exit");
printf("\n Enter ur choice :");
scanf("%d",&choice);
switch(choice)
{
case 1:
do
{
New=get_node();
printf("\n Enter the element");
scanf("%d",&New->data);
if(root==NULL)
root=New;
else
insert(root,New);
printf("\n Do u want to enter moreelements?(Y/N)");
ans=getch();;
}while(ans=='Y');
break;
case 2:
printf("\n Enter the element which u want tosearch");
scanf("%d",&key);
tmp=search(root,key,&parent);
printf("\n Parent of the node %d is%d",tmp->data,parent->data);
break;
case 3:
printf("\n Enter 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("\n The Tree is :");
inorder(root);
}
break;
case 5:
exit(0);
}
}
while(choice!=5);
}
node *get_node()
{
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("\n %d Element is present",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,*temp_succ;
temp=search(root,key,&parent);
if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
temp_succ=temp->right;
while(temp_succ->left!=NULL)
{
parent=temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data;
parent->right=NULL;
printf("\n Now delete 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("\n Now Delete 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("\n Now Delete it !");
return;
}
if(temp->left==NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
printf("\n Now Delete it !");
return;
}
}
void inorder(node *temp)
{
if(temp!=NULL)
{
inorder(temp->left);
printf("\n %d",temp->data);
inorder(temp->right);
}
}
Output : 



Output:
Program for BinarySearch Tree
1. Create
2.  Search
3. Delete
4. Display
5. Exit
Enter your choice: 1
Enter the Element: 100
Do you want to enter more element?(Y/N) : Y
Enter the Element: 200
Do you want to enter more element?(Y/N) : Y
Enter the Element: 300
Do you want to enter more element?(Y/N) : Y
Enter the Element: 400
Do you want to enter more element?(Y/N) : Y
Enter the Element: 500
Do you want to enter more element?(Y/N) : N
  Program for Binary
Search Tree
1. Create
2.  Search
3. Delete
4. Display
5. Exit
Enter your choice: 2
Enter the element you wish to search: 200
200 Element is present
Parent node of 200 is 100
Program for Binary
Search Tree
1. Create
2.  Search
3. Delete
4. Display
5. Exit
Enter your choice: 4
The Tree is
100
200
300
400
500
Program for Binary
Search Tree
1. Create
2.  Search
3. Delete
4. Display
5. Exit
Enter your choice: 3
Enter the element you wish to delete: 300
300 element is present!
Now Deleted!!
Program for Binary
Search Tree
1. Create
2.  Search
3. Delete
4. Display
5. Exit
Enter your choice: 4
The Tree is
100
200
400
500