#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;
int count = 0;
NODE maximum(NODE root)
{
    NODE cur;
    if (root == NULL)
        return root;
    cur = root;
    while (cur->rlink != NULL)
    {
        cur = cur->rlink;
    }
    return cur;
}

NODE minimum(NODE root)
{
    NODE cur;
    if (root == NULL)
        return root;
    cur = root;
    while (cur->llink != NULL)
    {
        cur = cur->llink;
    }
    return cur;
}

int count_nodes(NODE root)
{
    if (root == NULL)
        return 0;
    return 1 + count_nodes(root->llink) + count_nodes(root->rlink);
}

int max(int a, int b)
{
    return (a > b) ? a : b;
}
int height(NODE root)
{
    if (root == NULL)
        return 0;
    return 1 + max(height(root->llink), height(root->rlink));
}

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;
}
int main()
{
    NODE root = NULL;
    NODE max, min;
    int item, choice, ht;
    printf("Binary Search Tree Operations\n");
    while (1)
    {
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:scanf("%d", &item);
               root = insert(item, root);
               break;
        case 2:if (root == NULL)
               {
                   printf("TREE is empty\n");
                   break;
               }
               count = count_nodes(root);
               printf("NUMBER OF NODES IN BST = %d\n", count);
               break;
        case 3:if (root == NULL)
               {
                   printf("TREE is empty\n");
                   break;
               }
               ht = height(root);
               printf("HEIGHT OF BST IS = %d\n", ht);
               break;
        case 4:if (root == NULL)
               {
                   printf("TREE is empty\n");
                   break;
               }
               min = minimum(root);
               printf("MINIMUM VALUE IN BST IS = %d\n", min->info);
               break;
        case 5:if (root == NULL)
              {
                  printf("TREE is empty\n");
                  break;
              }
            max = maximum(root);
            printf("MAXIMUM VALUE IN BST IS = %d\n", max->info);
            break;
        case 6:exit(0);
        default:printf("Invalid Choice\n");
        }
    }
    return 0;
}