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

typedef struct _BSTNode {
    char* name;  // like the value
    struct _BSTNode* left;
    struct _BSTNode* right;
} BSTNode;

void _insert(BSTNode** a_root, char* name) {
    if(*a_root == NULL) {  // if this tree is empty, then add the node here
        BSTNode* new_node = malloc(sizeof(*new_node));
        *new_node = (BSTNode) { .name = name, .left = NULL, .right = NULL };
        *a_root = new_node;
    }
    else if(strcmp(name, (*a_root) -> name) < 0) {  // is new name less than root's name
        _insert(&((*a_root) -> left), name);
    }
    else {
        _insert(&((*a_root) -> right), name);
    }
}

void print_bst(BSTNode const* root) {  // IN-ORDER TRAVERSAL:  left, root, right
    if(root != NULL) {  // DO NOT SAY if(root) {
        print_bst(root -> left);      // 1. Traverse the left subtree.
        printf("%s\n", root -> name); // 2. Visit the root.
        print_bst(root -> right);     // 3. Traverse the right subtree.
    }
}

void free_bst(BSTNode** a_root) {  // POST-ORDER TRAVERSAL:  left, right, root
    // IMPORTANT:  Free the root node LAST.  Otherwise, you lose addresses of children.
    if(*a_root != NULL) {
        free_bst(&((*a_root) -> left));
        free_bst(&((*a_root) -> right));
        free(*a_root);
        *a_root = NULL;
    }
}

int main(int argc, char* argv[]) {
    printf("\n\n\n\n\n\n\n");
    printf("______________________________\n");
    BSTNode* root = NULL;
    // Tree size is 0.

    _insert(&root, "delta");
    _insert(&root, "bravo");
    _insert(&root, "alpha");
    _insert(&root, "charlie");
    _insert(&root, "foxtrot");
    _insert(&root, "echo");
    _insert(&root, "golf");
    _insert(&root, "india");
    print_bst(root);
    free_bst(&root);
    assert(root == NULL);

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