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

// BST - with BUGS - this will leak memory a lot due to bug in insert(…)
//                   forgot to call destroy

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) {
    // CREATE new node
    BSTNode* new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };

    if(*a_root == NULL) { // If tree is empty...
        *a_root = new_node;
    }
    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) {
    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);

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