1// Aim: Program to perform Binary Search Tree (BST) operations (Insertion, Deletion).
2#include<stdio.h>
3#include<stdlib.h>
4
5struct node {
6    int data;
7    struct node *left;
8    struct node *right;
9};
10
11int ch , item ,flag = 0;
12struct node *root = NULL,*ptr=NULL,*parent=NULL,*new;
13
14void insert(){
15    printf("\nEnter item to insert: ");
16    scanf("%d", &item);
17    if(root == NULL){
18        struct node *new = (struct node *)malloc(sizeof(struct node));
19        new->data = item;
20        new->left = NULL;
21        new->right = NULL;
22        root = new;
23    }else{
24        ptr = root;
25        flag = 0;
26        while(ptr != NULL && flag == 0){
27            if(ptr->data == item){
28                printf("\nDuplicate item");
29                flag = 1;
30                return;
31            }else if(ptr->data > item){
32                parent = ptr;
33                ptr = ptr->left;
34            }else{
35                parent = ptr;
36                ptr = ptr->right;
37            }    
38        }
39        if(ptr == NULL){
40            struct node *new = (struct node *)malloc(sizeof(struct node));
41            new->data = item;
42            new->left = NULL;
43            new->right = NULL;
44            if(parent->data > item){
45                parent->left = new;
46            }else{
47                parent->right = new;
48            }
49        }   
50    }
51}
52
53void inorder(struct node *ptr){
54    if(ptr != NULL){
55        inorder(ptr->left);
56        printf("%d ",ptr->data);
57        inorder(ptr->right);
58    }
59}
60
61struct node *insucc(struct node *y){
62    while(y->left != NULL){
63        y = y->left;
64    }
65    return y;
66}
67
68void delete(int item){
69    if(root == NULL){
70        printf("\nTree is empty");
71        return;
72    }
73    else{
74        ptr = root;
75        flag = 0;
76        while(ptr != NULL && flag == 0){
77            if(ptr->data == item){
78                flag = 1;
79            }else if(ptr->data > item){
80                parent = ptr;
81                ptr = ptr->left;
82            }else{
83                parent = ptr;
84                ptr = ptr->right;
85            }
86        }
87        if(flag == 0){
88            printf("\nItem not found");
89            return;
90        }
91        else{
92        if(ptr->left == NULL && ptr->right == NULL){
93            if(parent->left == ptr){
94                parent->left = NULL;
95            }else{
96                parent->right = NULL;
97            }
98            free(ptr);
99        }else if(ptr->left != NULL && ptr->right == NULL){
100            if(parent->left == ptr){
101                parent->left = ptr->left;
102            }else{
103                parent->right = ptr->left;
104            }
105            free(ptr);
106        }else if(ptr->left == NULL && ptr->right != NULL){
107            if(parent->left == ptr){
108                parent->left = ptr->right;
109            }else{
110                parent->right = ptr->right;
111            }
112            free(ptr);
113        }else{
114            struct node *succ = insucc(ptr->right);
115            printf("\nInorder successor is %d",succ->data);
116            int x = succ->data;
117            delete(x);
118            ptr->data = x;
119        }
120        }
121    }
122}
123
124void main(){
125    int choice;
126    while(1){
127        printf("\n1. Insert\n2. Delete\n3. Inorder\n4. Exit\nEnter choice: ");
128        scanf("%d",&choice);
129        switch(choice){
130            case 1: insert();
131                    break;
132            case 2: printf("\nEnter item to delete: ");
133                    scanf("%d",&item);
134                    delete(item);
135                    break;
136            case 3: inorder(root);
137                    break;
138            case 4: exit(0);
139        }
140    }
141}
142