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

typedef struct _TreeNode {
    int value;
    struct _TreeNode* left;
    struct _TreeNode* right;
} TreeNode;

// How to insert a node in a BST:
//  - If root is empty, then replace root with new node.
//  - If value goes in the left,  then insert a node in the left  subtree (also a BST)
//  - If value goes in the right, then insert a node in the right subtree (also a BST)

void insert(int new_value, TreeNode** a_root) {
    if(*a_root == NULL) {
        *a_root = malloc(sizeof **a_root);
        **a_root = (TreeNode) { .value = new_value, .left = NULL, .right = NULL };
    }
    else if(new_value < (*a_root) -> value) {  // don't forget parentheses!
        insert(new_value, &(*a_root) -> left);
    }
    else {
        assert(new_value >= (*a_root) -> value);  // don't forget parentheses!
        insert(new_value, &(*a_root) -> right);
    }
}

void print_tree(TreeNode* root) {
    // We can only print a non-empty tree.
    if(root != NULL) {                     // IN-ORDER TRAVERSAL (remember this)
        print_tree(root -> left);          // - Traverse¹ the left subtree
        printf("[%d]\n", root -> value);   // - Visit² the root
        print_tree(root -> right);         // - Traverse¹ the right subtree
    }
}

void free_bst(TreeNode** a_root) {
    if((*a_root) != NULL) {
        free_bst(&(*a_root) -> left);
        free_bst(&(*a_root) -> right);
        free(*a_root);
        *a_root = NULL;
    }
}



// ¹ "traverse" means do that entire operation the subtree.  This is a recursive call.
// ² "visit" means to do an operation to a single node.

int main(int argc, char* argv[]) {
    // append(4, &head, &tail)  // linked lists
    TreeNode* root = NULL;   // size == 0  (# of nodes in entire tree)
    insert(4, &root);        // size == 1
    insert(2, &root);        // size == 2
    insert(6, &root);        // size == 3
    insert(1, &root);        // size == 4
    insert(3, &root);        // size == 5
    insert(5, &root);        // size == 6
    insert(7, &root);        // size == 7
    print_tree(root);

    free_bst(&root);
    assert(root == NULL); // (assertion failed)

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