1// Aim: Program to perform Binary Tree operations (Linked representation).
2#include <stdio.h>
3#include <stdlib.h>
4
5struct node {
6    int data;
7    struct node* left;
8    struct node* right;};
9
10struct node *root = NULL, *loc = NULL, *ploc = NULL;
11int key, item;
12
13struct node* create_node(int data) {
14    struct node* new_node = (struct node*)malloc(sizeof(struct node));
15    new_node->data = data;
16    new_node->left = NULL;
17    new_node->right = NULL;
18    return new_node;}
19
20
21void build(struct node* ptr) {
22    int ch;
23    printf("\nEnter item: ");
24    scanf("%d", &ptr->data);
25    printf("\nCreate left child for %d? Enter 0 for yes: ", ptr->data);
26    scanf("%d", &ch);
27    if (ch == 0) {
28        ptr->left = create_node(0);
29        build(ptr->left);}
30    printf("\nCreate right child for %d? Enter 0 for yes: ", ptr->data);
31    scanf("%d", &ch);
32    if (ch == 0) {
33        ptr->right = create_node(0);
34        build(ptr->right);}}
35
36
37void inorder(struct node* ptr) { 
38    if (ptr == NULL)
39        return;
40    inorder(ptr->left);
41    printf("%d ", ptr->data);
42    inorder(ptr->right);}
43
44
45int search(struct node* par, struct node* ptr, int key) {
46    if (ptr != NULL) {
47        if (ptr->data == key) {
48            ploc = par;
49            loc = ptr;
50            return 1;
51        } else {
52            if (search(ptr, ptr->left, key) || search(ptr, ptr->right, key)) {
53                return 1;}}}
54    return 0;}
55
56
57
58void insert(struct node* ptr) {
59    printf("\nEnter item to insert: ");
60    scanf("%d", &item);
61    
62    printf("\nEnter key to search for insertion position: ");
63    scanf("%d", &key);
64
65    loc = NULL;
66    if (!search(NULL, root, key)) {
67        printf("\nKey not found\n");
68        return;}
69    printf("\nInsert %d as left child of %d? Enter 0 for yes: ", item, loc->data);
70    int ch;
71    scanf("%d", &ch);
72    if (ch == 0 && loc->left == NULL) {
73        loc->left = create_node(item);
74    } else if (ch == 0 && loc->left != NULL) {
75        printf("\nLeft child already exists\n");}
76    printf("\nInsert %d as right child of %d? Enter 0 for yes: ", item, loc->data);
77    scanf("%d", &ch);
78    if (ch == 0 && loc->right == NULL) {
79        loc->right = create_node(item);
80    } else if (ch == 0 && loc->right != NULL) {
81        printf("\nRight child already exists\n");}}
82
83
84void delete_node() {
85    printf("\nEnter key to delete: ");
86    scanf("%d", &key);
87    loc = NULL;
88    if (!search(NULL, root, key)) {
89        printf("\nKey not found\n");
90        return;}
91    if (loc->left == NULL && loc->right == NULL) {
92        if (ploc->left == loc)
93            ploc->left = NULL;
94        else
95            ploc->right = NULL;
96        free(loc);
97    } else {
98        printf("Node is not a leaf, can't delete\n");}}
99
100
101int main() {
102    int choice;
103    root = create_node(0);
104    while (1) {
105        printf("1. Build Tree\n2. Display Tree\n3. Search Key\n4. Insert Item\n5. Delete Item\n6. Exit\nEnter your choice: ");
106        scanf("%d", &choice);
107        switch (choice) {
108            case 1:
109                build(root);
110                break;
111            case 2:
112                printf("Inorder traversal: ");
113                inorder(root);
114                printf("\n");
115                break;
116            case 3:
117                printf("\nEnter key to search: ");
118                scanf("%d", &key);
119                loc = NULL;
120                if (!search(NULL, root, key))
121                    printf("\nKey not found\n");
122                else
123                    printf("\nKey found\n");
124                break;
125            case 4:
126                insert(root);
127                break;
128            case 5:
129                delete_node();
130                break;
131            case 6:
132                exit(0);
133            default:
134                printf("Invalid choice! Please enter a valid option.\n");}}
135    return 0;}