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

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

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

void stack_push(StackNode** a_top, char ch) {
    StackNode* new_top = malloc(sizeof(*new_top)); // NO (StackNode*)malloc, NO sizeof(StackNode)
    *new_top = (StackNode) { .next = NULL, .ch = ch };  // 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) -> ch == ch);  // Top should have the character we just pushed.
}

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

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
    stack_push(root)
}

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);

    // Free
    destroy_tree(&root);

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