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

typedef struct _Node {
    int value;
    struct _Node* left;
    struct _Node* right;
} Node;

Node* _create_node(int value) {
    Node* node = malloc(sizeof(*node));
    node->value = value;
    node->left  = NULL;
    node->right = NULL;
    return node;
}

void insert(Node** a_root, int value) {
    // insert(…) for trees is very similar to append(…) for linked lists,
    // except that instead of always adding to the tail, we add to either
    // .left or .right.  Also, we normally use recursion, since we can't
    // keep the address of the tail handy.
    if(*a_root == NULL) {  // If this tree (possibly a subtree) is empty…
        *a_root = _create_node(value);
    }
    else if(value <= (*a_root) -> value) {
        insert(&(*a_root) -> left, value);
    }
    else {
        assert(value > (*a_root) -> value);
        insert(&(*a_root) -> right, value);
    }
}

void destroy(Node** a_root) {
    // POST-ORDER TRAVERSAL
    if(*a_root != NULL) {
        // Destroy left  subtree -- recursive call to destroy(…)
        destroy(& (*a_root) -> left);

        // Destroy right subtree -- recursive call to destroy(…)
        destroy(& (*a_root) -> right);

        // Destroy root ----------- free(…)
        free(*a_root);

        // Set root (in caller's stack frame) to NULL (i.e., empty tree).
        *a_root = NULL;
    }
}

void print_bst(Node* root) {
    // IN-ORDER TRAVERSAL

    // For empty tree, do nothing
    if(root != NULL) {

        // Print the left subtree
        print_bst(root -> left);

        // Print the root
        printf("%d\n", root -> value);

        // Print the right subtree
        print_bst(root -> right);
    }
}


int main(int argc, char* argv[]) {
    // Make empty tree
    Node* root = NULL;  // a valid empty tree

    insert(&root, 4);
    insert(&root, 2);
    insert(&root, 4);
    insert(&root, 7);
    insert(&root, 9);
    insert(&root, 0);
    insert(&root, 7);
    insert(&root, 2);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 6);
    print_bst(root);

    destroy(&root);
    return EXIT_SUCCESS;
}
/*
    // Assign all fields
    Node temp = {
        .value = value,
        .left  = NULL,
        .right = NULL
    };
    *node = temp; // Yes, you can assign all of the fields in one statement.
*/
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */