#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
        if(root -> left != NULL) {
            print_bst(root -> left);  // RESURSIVE CALL
        }
        // Print value at the root.
        printf("[%d] ", root -> value);
        // Print right subtree
        if(root -> right != NULL) {
            print_bst(root -> right);  // RESURSIVE CALL
        }
    }
}

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

int main(int argc, char* argv[]) {
    // Empty tree (size==0)
    BSTNode* root = NULL;
    print_bst_pretty(root);

    // Insert 4 into the BST
    BSTNode* new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = 4, .left = NULL, .right = NULL };
    root = new_node;
    print_bst_pretty(root);

    // Insert 2 into the BST
    new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = 2, .left = NULL, .right = NULL };
    root -> left = new_node;
    print_bst_pretty(root);

    // Insert 1 into the BST
    new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = 1, .left = NULL, .right = NULL };
    root -> left -> left = new_node;
    print_bst_pretty(root);

    // Insert 3 into the BST
    new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = 3, .left = NULL, .right = NULL };
    root -> left -> right = new_node;
    print_bst_pretty(root);

    // Insert 6 into the BST
    new_node = malloc(sizeof(*new_node));
    *new_node = (BSTNode) { .value = 6, .left = NULL, .right = NULL };
    root -> right = new_node;
    print_bst_pretty(root);

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