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


int totalElem = 8;

typedef struct BST {
    int data;
    struct BST *left;
    struct BST *right;
} nodeBST;

nodeBST* addNode(int data);
void addNodeToBST(nodeBST *root, nodeBST *node);
void traverse(nodeBST *root);
void createBST(int arr[]);
void iterativeInorder(nodeBST *root);

int main()
{
    int arr[10] = {20,9,5,15,4,6,30,35};

    createBST(arr);

    return 0;
}

void MorrisInorder(nodeBST *root) {
    nodeBST* current,*pre;
    current=root;
    while(current!=NULL) {
        if(current->left==NULL) {
            printf("%d ",current->data);
            current=current->right;
        }
        else {
            pre=current->left;
            while(pre->right != NULL && pre->right !=current)
                pre=pre->right;
            if(pre->right==NULL) {
                printf("Link %d, %d\n", pre->data, current->data);
                pre->right=current;
                current=current->left;
            }
            else {
                pre->right=NULL;
                printf("%d ",current->data);
                current=current->right;
            }
        }
    }
}

// Recursive inorder traverse
void traverse(nodeBST *root)
{
    if (root == NULL) {
        return;
    } else {
        traverse(root->left);
        printf("%d ", root->data);
        traverse(root->right);
    }

    return;
}

void createBST(int arr[])
{
    nodeBST *node;
    nodeBST *root;
    int i = 0;
    
    for (i = 0; i < totalElem; i++) {
        node = addNode(arr[i]);
        if (node == NULL) {
            return;
        }

        if (i == 0) {
            root = node;
            continue;
        }

        addNodeToBST(root, node);
    }

    printf("Recursive Inorder:\n");
    traverse(root);
    printf("\n\nMorris Inorder:\n");
    MorrisInorder(root);
    printf("\n\nIterative Inorder:\n");
    iterativeInorder(root);
}

nodeBST* addNode(int data)
{
    nodeBST *node = (nodeBST*)calloc(1, sizeof(nodeBST));

    if (node == NULL) {
        return NULL;
    }

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void addNodeToBST(nodeBST *root, nodeBST *node)
{
    while(root != NULL) {
        if (node->data < root->data) {
            if (root->left != NULL) {
                root = root->left;
            } else {
                root->left = node;
                return;
            }
        } else {
            if (root->right != NULL) {
                root = root->right;
            } else {
                root->right = node;
                return;
            }
        }
    }

    return;
}

typedef struct stack {
    nodeBST* node;
    struct stack* next;
} stackNode;

stackNode* head;
stackNode* top;

void createStack()
{
    stackNode* root = (stackNode*)malloc(sizeof(stackNode));

    if (root == NULL) {
        //ASSERT
    }

    root->node = NULL;
    root->next = NULL;

    head = root;
    top = root;
}

void push(nodeBST* treeNode)
{
    stackNode* temp = (stackNode*)malloc(sizeof(stackNode));
    if (temp == NULL) {
        //ASSERT
    }

    temp->node = treeNode;
    temp->next = head->next;
    head->next = temp;

    top = head->next;
}

int isStackEmpty()
{
    if (head->next == NULL) {
        return 1;
    }

    return 0;
}

nodeBST* pop()
{
    stackNode* temp;

    if (!isStackEmpty()) {
        temp = top;
        head->next = top->next;

        if (head->next == NULL) {
            top = head;
        } else {
            top = head->next;
        }

        return temp->node;
    }

    return head->node;
}

// Iterative
// 1) Create an empty stack S.
// 2) Initialize current node as root
// 3) Push the current node to S and set current = current->left until current is NULL
// 4) If current is NULL and stack is not empty then 
//      a) Pop the top item from stack.
//      b) Print the popped item, set current = current->right
//      c) Go to step 3.
// 5) If current is NULL and stack is empty then we are done.

void iterativeInorder(nodeBST *root)
{
    createStack();

    while(1) {
        if (root != NULL) {
            // Keep pushing in the stack
            push(root);
            root = root->left;
        } else {
            if (isStackEmpty()) {
                break;
            }

            root = pop();
            printf("%d ", root->data);

            root = root->right;
        }
    }
}