#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 preorder(NODE root)
{
    if (root == NULL)
        return;
    printf("%d ", root->info);
    preorder(root->llink);
    preorder(root->rlink);
}
void postorder(NODE root)
{
    if (root == NULL)
        return;
    postorder(root->llink);
    postorder(root->rlink);
    printf("%d ", root->info);
}
void inorder(NODE root)
{
    if (root == NULL)
        return;
    inorder(root->llink);
    printf("%d ", root->info);
    inorder(root->rlink);
}

void main()
{
    NODE root;
    int item, choice;
    root = NULL;
    for (;;)
    {
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:scanf("%d", &item);
               root = insert(item, root);
               break;
        case 2:if (root == NULL)
               {
                   printf("BST Empty\n");
               }
               else
               {
                   printf("PREORDER TRAVERSAL OF BINARY SEARCH TREE\n");
                   preorder(root);
                   printf("\n");
               }
               break;
        case 3:if (root == NULL)
               {
                   printf("BST Empty\n");
               }
               else
               {
                   printf("INORDER TRAVERSAL OF BINARY SEARCH TREE\n");
                   inorder(root);
                   printf("\n");
               }
               break;
        case 4:if (root == NULL)
               {
                   printf("BST Empty\n");
               }
               else
               {
                   printf("POSTORDER TRAVERSAL OF BINARY SEARCH TREE\n");
                   postorder(root);
                   printf("\n");
               }
               break;
        case 5:exit(0);
        default:printf("Invalid Choice\n");
                break;
        }
    }
}