#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#pragma pack(1)  // Tell compiler not to padding between struct fields

// BST - CORRECT

// Okay to copy/adapt COMMENTS from this file (but not code)

typedef struct _BSTNode {
    int value;                //  =4 bytes¹
    struct _BSTNode* left;    //  =8 bytes¹
    struct _BSTNode* right;   //  =8 bytes¹
} BSTNode;                    // =20 bytes¹
// ¹ on our platform

void insert(int value, BSTNode** a_root) {
    // If tree is empty, then insert the value as the root of this tree.
    if(*a_root == NULL) {
        // CREATE new node
        BSTNode* new_node = malloc(sizeof(*new_node));
        *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };

        // CONNECT new node to the tree
        *a_root = new_node;
    }
    // Otherwise, insert in either the left or right subtree, depending on the value.
    else if(value < (*a_root) -> value) {
        insert(value, &((*a_root) -> left));
    }
    else if(value >= (*a_root) -> value) {
        insert(value, &((*a_root) -> right));
    }
}

void print_tree_in_order(BSTNode* root) {  // IN-ORDER traversal:  left, root, right
    if(root != NULL) {
        print_tree_in_order(root -> left);  // print the left subtree (recursively)
        printf("-[%d]-", root -> value);    // print value in the root
        print_tree_in_order(root -> right); // print the right subtree (recursively)
    }
}

void destroy_tree(BSTNode** a_root) {  // 
    if(*a_root != NULL) {
        destroy_tree(&((*a_root) -> left));
        assert((*a_root) -> left == NULL);  // left subtree has been destroyed and is empty
        destroy_tree(&((*a_root) -> right));
        assert((*a_root) -> right == NULL);

        free(*a_root);   // deallocate
        *a_root = NULL;  // set to NULL to indicate that it is empty
    }
    assert(*a_root == NULL); // Tree must be empty
}

int main(int argc, char* argv[]) {
    // Empty list
    BSTNode* root = NULL;

    // Insert a value
    insert(4, &root);
    insert(2, &root);
    insert(6, &root);
    insert(1, &root);
    insert(3, &root);
    insert(5, &root);
    insert(7, &root);

    // Print
    print_tree_in_order(root);

    // Free
    destroy_tree(&root);

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