#include <stdio.h>
#include <stdlib.h>

#define MALLOC(p,n,type) \
p = (type*)malloc(n * sizeof(type)); \
if (p == NULL) {\
    printf("insufficient memory\n"); \
    exit(0); \
}

struct node
{
    int info;
    struct node *llink;
    struct node *rlink;
};
typedef struct node* NODE;
NODE insert(int item, NODE root) 
{
    NODE temp, cur, prev;
    MALLOC(temp, 1, struct node);
    temp->info = item;
    temp->llink = NULL;
    temp->rlink = NULL;
    if (root == NULL) 
    return temp;
    prev = NULL;
    cur = root;
    while (cur != NULL) 
    {
        prev = cur;
        if (item == cur->info) 
        {
            printf("Duplicate items are not allowed\n");
            free(temp);
            return root;
        }
        if (item < cur->info)
            cur = cur->llink;
        else
            cur = cur->rlink;
    }
    if (item < prev->info)
        prev->llink = temp;
    else
        prev->rlink = temp;
    return root;
}

void inorder(NODE root)
{
    if (root == NULL) 
    return;
    inorder(root->llink);
    printf("%d ", root->info);
    inorder(root->rlink);
}


NODE search(int item, NODE root)
{
    NODE cur;
    if (root == NULL) return NULL;  
    cur = root;
    while (cur != NULL)
    {  
        if (item == cur->info) 
        return cur;  
        if (item < cur->info)
            cur = cur->llink;  
        else
            cur = cur->rlink;  
    }
    return NULL;  
}
NODE delete(int item, NODE root) 
{
    NODE cur, parent, suc, q;
    if (root == NULL) 
    {
        printf("Cannot delete - %d is not found or BST empty\n", item);
        return root;
    }
    parent = NULL, cur = root; 
    while (cur != NULL)
    {
        if (item == cur->info) break;
        parent = cur;
        cur = (item < cur->info) ? cur->llink : cur->rlink;
    }
    if (cur == NULL)
    {
        printf("Cannot delete - %d is not found or BST empty\n", item);
        return root;
    }
    if (cur->llink == NULL)  
        q = cur->rlink;  
    else if (cur->rlink == NULL)  
        q = cur->llink;  
    else
    {
        suc = cur->rlink;  
        while (suc->llink != NULL)
            suc = suc->llink;
        suc->llink = cur->llink;  
        q = cur->rlink;
    }
    if (parent == NULL) 
    {
        printf("%d is found and deleted from BST\n", item);
        free(cur);
        return q;  
    }
   
    if (cur == parent->llink)
        parent->llink = q;
    else
        parent->rlink = q;
    printf("%d is found and deleted from BST\n", item);
    free(cur);
    return root;
}

void main() 
{
    NODE root, search_node;
    int item, choice, item_search, item_deleted;
    root = NULL;
    printf("Binary Search Tree Operations\n");
    for (;;)
    {
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:scanf("%d", &item);
                   root = insert(item, root);
                   break;
            case 2:scanf("%d", &item_deleted);
                   root = delete(item_deleted, root);
                   break;
            case 3:if (root == NULL) 
                   {
                       printf("BST EMPTY\n");
                   } 
                   else 
                   {
                       printf("INORDER TRAVERSAL OF BST: ");
                       inorder(root);
                       printf("\n");
                   }
                   break;
            case 4:scanf("%d", &item_search);
                   search_node = search(item_search, root);
                   if (search_node == NULL)
                   printf("Search Unsuccessful %d is not found in BST\n", item_search);
                   else
                   printf("Search Successful %d is found in BST\n", item_search);
                break;

           case 5:exit(0);
           case 6:printf("Invalid Choice\n");
        }
    }
}