//Implement binary search tree
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left, *right;
};                                      //Creation of a node with pointers pointing to left and right of the node

struct node *newnode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}                                                        //Creation of new node

void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}                                                //Function for inorder traversal, which infact, is sorting the elements in ascending order


struct node *insert(struct node *node, int data)
{
    if (node == NULL)
        return newnode(data);
    if (data < node->data)
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);
    return node;
}                                                               //Insertion of new node

struct node *minvalue(struct node *node)
{
    struct node *current = node;
    while (current && current->left != NULL)
    {
        current = current->left;
    }
    return current;
}

struct node *deletenode(struct node *root, int data)
{
    if (root == NULL)
        return root;
    if (data < root->data)
        root->left = deletenode(root->left, data);
    else if (data > root->data)
        root->right = deletenode(root->right, data);
    else
    {
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        struct node *temp = minvalue(root->right);
        root->data = temp->data;
        root->right = deletenode(root->right, temp->data);
    }
    return root;
    
}

struct node *search(struct node *root, int data)
{
    if (root == NULL || root->data == data)
        return root;
    if (root->data < data)
        return search(root->right, data);
    return search(root->left, data);
}                                                           //Recursive calling for left and right nodes

int main()
{
    struct node *root = NULL;
    int a, num;

    do
    {
        printf("\nEnter 1 for insertion, 2 for deletion, 3 for searching, 4 for inorder traversal, and 5 to exit\n");
        scanf("%d", &a);
        switch (a)
        {
        case 1:
            printf("Enter data to be inserted: ");
            scanf("%d", &num);
            root = insert(root, num);                           //Assign the returned value to the root variable, same on 114
            break;
        case 2:
            printf("Enter node to be deleted: ");
            scanf("%d", &num);
            root = deletenode(root, num);
            break;
        case 3:
            printf("Enter element to search: ");
            scanf("%d", &num);
            if (search(root, num) != NULL)
                printf("Element %d is present in the tree.\n", num);
            else
                printf("Element %d is not found in the tree.\n", num);
            break;
        case 4:
            printf("Inorder traversal: ");
            inorder(root);
            printf("\n");
            break;
        case 5:
            printf("Program terminated!\n");
            break;
        default:
            printf("Enter a valid key!\n");
        }
    } while (a != 5);

    return 0;
}