//Experiment-5
include<stdio.h>
include<conio.h>
include<stdlib.h>
struct node
{
int data;
struct node *left *right;
};
struct node *r=NULL *new1;
void insert(struct node *r struct node *nn);
void preorder(struct node *r);
void inorder(struct node *r);
void postorder(struct node *r);
void search();
void main()
{
int ch;
char m;
//clrscr();
printf("\n PROGRAM FOR IMPLEMENTATION OF BINARY SEARCH\n");
printf("\n TREE(BST) USING LINKED LIST \n");
do{
printf("\n1.CREATE BST\n2.PREORDER TRAVERSAL \n3.INORDER
TRAVERSAL\n4.POSTORDER TRAVERSAL \n5.SEARCH\n6.EXIT\n");
printf("\n ENTER YOUR CHOICE \n");
scanf("%d" &ch);// ch = 6
switch(ch)
{
case 1: do
{
new1=(struct node*)malloc(sizeof(struct node));
printf("\n ENTER THE DATA=>\n");
scanf("%d" &new1->data);//20
new1->left=NULL;
new1->right=NULL;
if(r==NULL)// false
{
r=new1;
}
else
{
insert(r new1);
}
printf("\n DO YOU WANT TO CONTINUE (y/n)=>\n");
m=getche();
}while(m=='y'||m=='Y');//false
break;
case 2: preorder(r);
break;
case 3: inorder(r);
break;
case 4: postorder(r);
break;
case 5: search();
break;
}
}while(ch!=6);//false
}
void insert(struct node *r struct node *nn)// r =1000 nn= 3000
{
if(nn->data<r->data)// 20< 10 false
{
if(r->left==NULL)// true
r->left=nn;
else
insert(r->left nn);
}
else
{
if(r->right==NULL)// true
r->right=nn;
else
insert(r->right nn);
}
}
void preorder(struct node *r)// r = NULL
{
if(r==NULL)// True
{ return;}
printf("%d\t" r->data);//
preorder(r->left);
preorder(r->right);
}
void inorder(struct node *r)// r = NULL
{
if(r==NULL)// true
{ return;
}
inorder(r->left);//
printf("%d\t" r->data);
inorder(r->right);
}
void postorder(struct node *r)// r = NULL
{
if(r==NULL)// false
{ return;
}
postorder(r->left);
postorder(r->right);
printf("%d\t" r->data);
}
void search()
{
int key flag=0;
struct node *temp;
temp=r;
if(temp==NULL)//false
printf("\n BST IS EMPTY SEARCH NOT POSSIBLE \n");
else
{
printf("\n ENTER THE DATA TO BE SEARCHED \n");
scanf("%d" &key);//key = 5
while(temp!=NULL)//true
{
if(key<temp->data)// 5 < 10 true
{
temp=temp->left;
}
else
{
temp=temp->right;
}
if(temp->data==key)//true
{
flag=1;
break;
}
}
if(flag==1)
{
printf("\n NODE %d IS PRESENT IN BST .\n" key);
}
else
{
printf("\n NODE %d IS ABSENT IN BST \n" key);
}
}
}
OUTPUT :-
Input 1: Create a Binary Search Tree (BST)
```
PROGRAM FOR IMPLEMENTATION OF BINARY SEARCH
TREE(BST) USING LINKED LIST
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
1
ENTER THE DATA=>
10
DO YOU WANT TO CONTINUE (y/n)=>
y
ENTER THE DATA=>
5
DO YOU WANT TO CONTINUE (y/n)=>
y
ENTER THE DATA=>
15
DO YOU WANT TO CONTINUE (y/n)=>
n
```
Input 2: Preorder Traversal
```
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
2
10 5 15
```
Input 3: Inorder Traversal
```
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
3
5 10 15
```
Input 4: Postorder Traversal
```
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
4
5 15 10
```
Input 5: Search for a node
```
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
5
ENTER THE DATA TO BE SEARCHED
5
NODE 5 IS PRESENT IN BST .
```
Input 6: Exit
```
1.CREATE BST
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.SEARCH
6.EXIT
ENTER YOUR CHOICE
6
```
