#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#pragma pack(1)  // Tell compiler not to padding between struct fields

/********************************************************************
|* SEE iterative_tree_traversals.c.  It is the 3:00 PM with some improvements
|* for clarity made later.
|*
|* This is the 1:30pm version.
\*/

typedef struct _BSTNode {
    int value;                //  =4 bytes¹
    struct _BSTNode* left;    //  =8 bytes¹
    struct _BSTNode* right;   //  =8 bytes¹
} BSTNode;                    // =20 bytes¹

typedef struct _StackNode {
    BSTNode* value;
    struct _StackNode* next;
} StackNode;

void stack_push(StackNode** a_top, BSTNode* value) {
    StackNode* new_top = malloc(sizeof(*new_top));
    *new_top = (StackNode) { .next = NULL, .value = value };  // Compound literal
    if(*a_top != NULL) {  // If stack is not initially empty...
        new_top -> next = *a_top;   // make the new top refer to the existing top
    }
    *a_top = new_top; // new top becomes the top of the stack
    assert(*a_top != NULL);  // Just added something, so can't possibly be empty now.
    assert((*a_top) -> value == value);  // Top should have the character we just pushed.
}

BSTNode* stack_pop(StackNode** a_top) {  // Usage:  Must not be called with an empty stack.
    StackNode* old_top = *a_top;
    BSTNode* value = old_top -> value;
    *a_top = old_top -> next;
    free(old_top);
    return value;
}

bool stack_is_empty(StackNode* top) {
    return (top == NULL);
}

void insert(int value, BSTNode** a_root) {
    // If tree is empty, then insert the value as the root of this tree.
    if(*a_root == NULL) {
        // CREATE new node
        BSTNode* new_node = malloc(sizeof(*new_node));
        *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };

        // CONNECT new node to the tree
        *a_root = new_node;
    }
    // Otherwise, insert in either the left or right subtree, depending on the value.
    else if(value < (*a_root) -> value) {
        insert(value, &((*a_root) -> left));
    }
    else if(value >= (*a_root) -> value) {
        insert(value, &((*a_root) -> right));
    }
}

void print_tree_in_order(BSTNode* root) {  // IN-ORDER traversal:  left, root, right
    StackNode* top = NULL;  // create empty stack
    BSTNode* curr = root;
    while(curr != NULL || top != NULL) {
        if(curr != NULL) {
            stack_push(&top, curr);  // ex: "Push the 4 node"
            curr = curr -> left;     // ex: "Go to its left subtree"
        }
        else {
            curr = stack_pop(&top);  // ex: "Pop gives us the 1 node"
            printf("curr -> value == %d\n", curr -> value);  // "Print the '1'"
            curr = curr -> right;    // ex: Will lead to pushing the right next time.
        }
    }
}

void print_tree_pre_order(BSTNode* root) {  // PRE-ORDER traversal:  root, left, right
    if(root != NULL) {
        StackNode* top = NULL;  // create empty stack
        stack_push(&top, root);
        while(top != NULL) {
            BSTNode* curr = stack_pop(&top);
            if(curr != NULL) {
                printf("curr -> value == %d\n", curr -> value);
                stack_push(&top, curr -> right);
                stack_push(&top, curr -> left);
            }
        }
    }
}

void destroy_tree(BSTNode** a_root) {  // 
    if(*a_root != NULL) {
        destroy_tree(&((*a_root) -> left));
        assert((*a_root) -> left == NULL);  // left subtree has been destroyed and is empty
        destroy_tree(&((*a_root) -> right));
        assert((*a_root) -> right == NULL);

        free(*a_root);   // deallocate
        *a_root = NULL;  // set to NULL to indicate that it is empty
    }
    assert(*a_root == NULL); // Tree must be empty
}

int main(int argc, char* argv[]) {
    // Empty list
    BSTNode* root = NULL;

    // Insert a value
    insert(4, &root);
    insert(2, &root);
    insert(6, &root);
    insert(1, &root);
    insert(3, &root);
    insert(5, &root);
    insert(7, &root);

    // Print
    //print_tree_in_order(root);
    print_tree_pre_order(root);

    // Free
    destroy_tree(&root);

    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */