#include<stdio.h>
typedef struct BinarySearchTree
{
    int key;
    struct BinarySearchTree *left;
    struct BinarySearchTree *right;
}BST;
int *arr = NULL;

BST *head = NULL;
void create(int k)
{
    BST *x = (BST*)malloc(sizeof(BST));
    BST *r1 = head, *r2;
    x->key = k;
    x->left = x->right = NULL;
    if(!head)
    {
        head = x;
        return;
    }
    while (r1)
    {
        r2 = r1; //stores the address of the last node visited by r1
        if( k < r1->key)
        {
            r1 = r1->left;
        }
        else
        {
            r1 = r1->right;
        }
    }
    if (k < r2->key)
    {
        r2->left = x;
    }
    else
    {
        r2->right = x;
    }
}
void inorder_iterative()
{
    printf("\n Inorder traversal of the Binary Search Tree is ------ \n");
    BST *r = head;
    do
    {
        while (r)
        {
            push(r);
            r = r->left;
        }
        r = pop();
        printf("\t %d", r->key);
        r = r->right;
    } while (r || top == -1);
}
void preorder_iterative()
{
    printf("\n Preorder traversal of the Binary Search Tree is ------ \n");
    BST *r = head;
    do
    {
        while (r)
        {
            printf("\t %d", r->key);
            push(r);
            r = r->left;
        }
        r = pop();
        r = r->right;
    } while (r || top == -1);
}
int main()
{
    int choice;
    do
    {
        printf("\n ----------Menu---------- ");
        printf("\n Press 1 to enter nodes in the Binary Search Tree.");
        printf("\n Press 2 to inorderly traverse the Binary Search Tree (iterative).");
        printf("\n Press 3 to inorderly traverse the Binary Search Tree (recursive).");
        printf("\n Press 4 to preorderly traverse the Binary Search Tree (iterative).");
        printf("\n Press 5 to inorderly traverse the Binary Search Tree (recursive).");
        printf("\n Press -1 to exit. ");
        printf("\n Enter choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1 :
}