#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
// AS ALWAYS:  Do not copy code from lecture examples (or anywhere else except code that
// you wrote yourself) without explicit permission from the instructor (me).

typedef struct _BSTNode {
    char const* name;
    struct _BSTNode* left;
    struct _BSTNode* right;
} BSTNode;

void insert(BSTNode** a_root, char const* name) {
    // If tree at *a_root is empty, then replace the empty tree with a tree of size = 1.
    if(*a_root == NULL) {
        BSTNode* new_root = malloc(sizeof(*new_root));
        *new_root = (BSTNode) { .name = name, .left = NULL, .right = NULL };
        *a_root = new_root;
    }
    // If name (to be inserted) is "less than" the name at *a_root, insert in left subtree.
    else if(strcmp(name, (*a_root) -> name) < 0) {
        insert(&((*a_root) -> left), name);
    }
    else {
        insert(&((*a_root) -> right), name);
    }
}

void print_bst(BSTNode const* root) {  // IN-ORDER traversal
    if(root != NULL) {  // … because printing an empty tree means printing nothing at all.
        print_bst(root -> left);      // 1. Traverse the left subtree.
        printf("%s\n", root -> name); // 2. Visit (print value of) the root
        print_bst(root -> right);     // 3. Traverse the right subtree.
    }
}

void free_bst(BSTNode** a_root) {  // POST-ORDER traversal
    // ⚠ IMPORTANT:  Free the subtrees «before» you free the root.
    if(*a_root != NULL) { // No need to free an empty tree.
        free_bst(&((*a_root) -> left));   // 1. Traverse the left subtree.
        free_bst(&((*a_root) -> right));  // 2. Traverse the right subtree.
        free(*a_root);                    // 3. Visit (free) the root node.
        *a_root = NULL;
    }
}

int main(int argc, char* argv[]) {
    BSTNode* root = NULL;
    // Tree has size = 0 (empty tree)
    
    insert(&root, "delta");
    insert(&root, "bravo");
    insert(&root, "alpha");
    insert(&root, "charlie");
    insert(&root, "foxtrot");
    insert(&root, "echo");
    insert(&root, "golf");
    insert(&root, "india");
    // Tree has size = 8 (8 nodes)
    
    print_bst(root);

    free_bst(&root);
    assert(root == NULL);

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