/* TREE TRAVERSALS:  IN-ORDER, PRE-ORDER, POST-ORDER
 *
 * This uses a binary search tree (BST) with 7 nodes: 1-2-3-4-5-6-7 (balanced with 4 as root).
 *
 * This is just a slight variant on the other example for today (bst_123.c).
 */

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

typedef struct _Node {
    int value;
    struct _Node* left;
    struct _Node* right;
} Node;

void print_bst_inorder(Node* root) { // IN-order because this is natural order
    if(root != NULL) {
        print_bst_inorder(root -> left);    // visit the left subtree
        printf("-%d-\n", root->value);      // visit the root
        print_bst_inorder(root -> right);   // visit the right subtree
    }
}

void print_bst_preorder(Node* root) { // PRE-order because visit root first
    if(root != NULL) {
        printf("-%d-\n", root->value);      // visit the root
        print_bst_preorder(root -> left);   // visit the left subtree
        print_bst_preorder(root -> right);  // visit the right subtree
    }
}

void print_bst_postorder(Node* root) { // POST-order because visit root last
    if(root != NULL) {
        print_bst_postorder(root -> left);  // visit the left subtree
        print_bst_postorder(root -> right); // visit the right subtree
        printf("-%d-\n", root->value);      // visit the root
    }
}

Node* _create_node(int value) {
    Node temp = { .value=value, .left=NULL, .right=NULL };
    Node* node = malloc(sizeof(*node));
    *node = temp;  // Yes, you can assign all of the fields with one statement.
    return node;
}

void insert(Node** a_root, int value) {
    if(*a_root == NULL) {
        *a_root = _create_node(value);
    }
    else if(value < (*a_root) -> value) {
        insert(&(*a_root) -> left, value);
    }
    else {
        insert(&(*a_root) -> right, value);
    }
}

void destroy(Node* root) {   // POST-ORDER traversal since we free *after* recursively
    if(root != NULL) {       // destroying both subtrees
        destroy(root -> left);
        destroy(root -> right);
        free(root);          // Visiting the root last
    }
}

int main(int argc, char* argv[]) {
    // Make a binary search tree (BST) with 7 nodes: 1-2-3-4-5-6-7 (balanced with 4 as root)
    Node* root = NULL;  // a valid empty tree
    insert(&root, 4);
    insert(&root, 2);
    insert(&root, 6);
    insert(&root, 1);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 7);

    printf("In-order\n");
    print_bst_inorder(root);

    printf("Pre-order\n");
    print_bst_preorder(root);

    printf("Post-order\n");
    print_bst_postorder(root);

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