#include<stdio.
h>
#include<stdlib.h>
struct tree{
int data;
struct tree *left;
struct tree *right ;
};
void printing(struct tree *root){
if(root == NULL)return ;
printing(root -> left);
printf("%d ",root -> data);
printing(root -> right);
}
struct tree* MinFromRight(struct tree* root){
if(root == NULL)return NULL;
while (root -> left != NULL)
{
root = root -> left;
}
return root;
}
struct tree *del(struct tree* root,int data){
if(root == NULL)return root;
if(root -> data == data){
if(root -> left == NULL && root -> right == NULL){
free(root);
return NULL;
}
if(root -> left != NULL && root -> right == NULL){
struct tree* temp = root-> left;
free(root);
return temp;
}
if(root -> right != NULL && root -> left == NULL){
struct tree *temp = root -> right;
free(root);
return temp;
}
if(root -> left != NULL && root -> right != NULL){
int min = MinFromRight(root -> right) -> data;
root -> data = min;
root -> right = del(root -> right,min);
return root;
}
}
else if(root -> data > data){
root -> left = del(root -> left,data);
}
else{
root -> right = del(root -> right,data);
}
return root;
}
struct tree *Mynode(struct tree *root,int data){
if(root == NULL){
struct tree *add = (struct tree*)malloc(sizeof(struct tree));
add -> data = data;
root = add;
return root;
}
if(data > root -> data){
root -> right = Mynode(root -> right,data);
}else{
root -> left = Mynode(root->left,data);
}
return root;
}
struct tree* input(struct tree* root){
int data;
scanf("%d",&data);
while (data != -1){
root = Mynode(root,data);
scanf("%d",&data);
}
return root;
}
void keyFind(struct tree* root,int key){
if(root == NULL)return ;
keyFind(root -> left,key);
if(root -> data == key){
printf("Key is present");
return ;
}
keyFind(root -> right,key);
}
int main(){
struct tree *root = NULL;
int dele;
printf("enter the data for inserting into BST => \n");
root = input(root);
printing(root);
while(1){
printf("\n1 For deletion\n2 For Insertion in BST\n3 For Key
element\n0 For delete The element\n");
int a;
scanf("%d",&a);
if(a == 0)break;
switch(a){
case 1:
int dele;
printf("Enter the deletion Data => ");
scanf("%d",&dele);
root = del(root,dele);
printing(root);
break;
case 2:
root = input(root);
printing(root);
break;
case 3:
int key;
printf("enter the Key to Find => ");
scanf("%d",&key);
keyFind(root,key);
break;
default:
printf("enter the Valid selection\n");
}
}
return 0;
}
