#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 level_order(NODE root)
{
    if (root == NULL)
    {
        printf("BST EMPTY - LOT/BFS NOT POSSIBLE\n");
        return;
    }
    NODE q[100], cur;
    int front = 0, rear = -1;
    q[++rear] = root;
    printf("LEVEL ORDER TRAVERSAL OF BINARY SEARCH TREE\n");
    while (front <= rear)
    {
        cur = q[front++];
        printf("%d ", cur->info);
        if (cur->llink != NULL)
            q[++rear] = cur->llink;
        if (cur->rlink != NULL)
            q[++rear] = cur->rlink;
    }
    printf("\n");
}

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:level_order(root);
                   break;
            case 3:exit(0);
            default:printf("Invalid Choice\n");
                    break;
        }
    }
}