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

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

void print_bst(BSTNode* root) {
    // Do nothing if the tree is empty.
    if(root != NULL) {
        // Print left subtree.
        print_bst(root -> left);  // RESURSIVE CALL

        // Print value at the root.
        printf("[%d] ", root -> value);

        // Print right subtree.
        print_bst(root -> right);  // RESURSIVE CALL
    }
}

void insert_into_bst(int value, BSTNode** a_root) {
    if(*a_root == NULL) {  // If tree is currently empty
        // Allocate space
        BSTNode* new_node = malloc(sizeof(*new_node));

        // Initialize fields in the node object.
        *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };

        // Set the root to our new node.
        *a_root = new_node;
    }
    else if(value < (*a_root) -> value) {
        insert_into_bst(value, &((*a_root) -> left));
    }
    else if(value >= (*a_root) -> value) {
        insert_into_bst(value, &((*a_root) -> right));
    }
}

void print_bst_pretty(BSTNode* root) {
    printf("BST:");
    print_bst(root);
    printf("\n");
}

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

    int numbers[7] = {4, 2, 1, 3, 6, 5, 7};
    for(int i = 0; i < 7; i++) {
        insert_into_bst(numbers[i], &root);
    }
    print_bst_pretty(root);

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