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

// In your code, you can and should follow the same pattern, but please make sure you
// can write it yourself.  Do not copy.  It is fine if your code comes out very similar.

// CAUTION: Remember to parenthesize (*a_root).


typedef struct _BSTNode {
    int value;
    struct _BSTNode* left;
    struct _BSTNode* right;
} BSTNode;

void insert(int value, BSTNode** a_root) {
    if(*a_root == NULL) {  // If tree is empty...
        BSTNode* new_node = malloc(sizeof *new_node);
        *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };
        *a_root = new_node;
    }
    else if(value < (*a_root) -> value) { // If value belongs in left subtree
        insert(value, &(*a_root) -> left);
    }
    else if(value >= (*a_root) -> value) { // If value belongs in left subtree
        insert(value, &(*a_root) -> right);
    }
}

void print_in_order(BSTNode* root) {
    if(root != NULL) {                   // IN-ORDER TRAVERSAL  (remember this)
        print_in_order(root -> left);    //  - Traverse left subtree
        printf("[%d]\n", root -> value); //  - Visit root node
        print_in_order(root -> right);   //  - Traverse right subtree
    }
}

void free_tree(BSTNode** a_root) {
    // We can only free a tree that contains node(s).
    if(*a_root != NULL) {                // POST-ORDER TRAVERSAL  (remember this)
        free_tree(&(*a_root) -> left);   //  - Traverse left subtree
        free_tree(&(*a_root) -> right);  //  - Traverse right subtree
        free(*a_root);                   //  - Visit the root
        *a_root = NULL;
    }
}

// PRE-ORDER TRAVERSAL  (remember this)
//  - Visit the root
//  - Traverse left subtree
//  - Traverse right subtree

int main(int argc, char* argv[]) {
    BSTNode* root = NULL;   // size=0
    // append(6, &head, &tail);  // not for BST
    insert(6, &root);
    insert(2, &root);
    insert(4, &root);
    insert(1, &root);
    insert(3, &root);
    insert(5, &root);
    insert(7, &root);
    print_in_order(root);

    free_tree(&root);
    assert(root == NULL);
    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */