/***********************************************************************
* BinaryTree.cpp
*
* A simple inplementation of a binary tree
*
* Written by Paul Bonamy - 24 January 2010
* Rewritten in pure C - 30 March 2010
************************************************************************/

#include <stdio.h>          // this replaces iostream for I/O tasks
#include <stdlib.h>         // malloc (replaces new) lives in here
#include "binarytree.h"     // we need the declaration of BINTREE nodes

/***********************************************************************
 * void bintree_insert(BINTREE **root, int v)
 *
 * Insert a given value into a particular tree.
 *
 * Because there may not actually be a root node yet, we have to be able
 * to allocate one and hand it back. To pull that off, we'll pass a
 * pointer to the pointer into the insert function. This way, we can modify
 * the *pointer itself*, rather than just the thing it's pointing to.
 * 
 * As a handy offshoot, the overall logic gets easier as we can traverse
 * until the root pointer no longer points to anything and then insert there
 * 
 * root -> pointer to a pointer to the root of the (local) tree
 * v -> value to add to tree
 * no return
 ***********************************************************************/
void bintree_insert(BINTREE ** root, int v) {
    if (*root == 0) { // we're out of tree, so we should create the new node
        // malloc needs to know how big a block of memory to allocate
        // and passes back a void pointer to it, so typecast
        BINTREE * newbie = (BINTREE*)malloc(sizeof(BINTREE));
        newbie->value = v;      // set the value of the node
        newbie->left = 0;       // we have to 0 out left and right manually
        newbie->right = 0;
        *root = newbie;         // now redirect the root pointer to connect
                                // to the new node
    }
    else {
        if (v < (*root) -> value) {
            // we need to insert to the left of the current node
            bintree_insert(&((*root)->left), v);
        }
        else if ((*root) -> value == v) {
            // the current node has the goal value, so do nothing. we're done
        }
        else {
            // we must need to insert to the right of the current node
            bintree_insert(&((*root)->right), v);
        }
    }
    
    return;
    
}

/***********************************************************************
 * void bintree_empty(BINTREE ** root)
 *
 * Delete all nodes in the tree and return. Does this by performing a
 * post-order traversal, deleting each node once its children have
 * been deleted.
 *
 * Note that, because we need to redirect the root pointer to 0
 * we'll need to receive a pointer-to-a-pointer to the root, rather
 * than just a pointer to same
 *
 * root -> pointer to pointer to root of the tree to delete / no return
 ***********************************************************************/
void bintree_empty(BINTREE ** root) {
    if (*root == 0) return;             // stop if we ran out of tree
    bintree_empty(&((*root)->left));    // delete left children
    bintree_empty(&((*root)->right));   // delete right children
    free(*root);                        // delete root node
    *root = 0;                          // flag root node as deleted
    return;
}

/*
 * we can implement something like a private function by only
 * providing a prototype in the .c file, not in the corresponding .h
 */
void bintree_print_helper(BINTREE * curr);

/***********************************************************************
 * void bintree_print(BINTREE * root)
 *
 * Print the contents of all nodes using in-order traversal. Relies
 * on a private, recursive helper for ease of use.
 *
 * Note that we don't actually change the tree, so we don't need to
 * pass a pointer-to-a-pointer to root, a normal pointer will do
 *
 * root -> pointer to root of the tree/ no return
 ***********************************************************************/
void bintree_print(BINTREE * root) {
    if( root == 0) {
        // printf will happily print strings. use \n to get a new line
        printf("empty\n");      // tree is empty, so say so
    }
    else {
        bintree_print_helper(root); // call the recursive printer, starting at root
        printf("\n");           // print out an endline when we're done printing
    }

    return;
}

/***********************************************************************
 * void BinaryTree::print_helper(Node* curr)
 *
 * Do an in-order traversal of the tree, printing node values as we go
 *
 * curr -> current node under examination / no return
 ***********************************************************************/
void bintree_print_helper(BINTREE * curr) {
    if (curr == 0) return;              // stop if we ran out of tree
    bintree_print_helper(curr -> left); // print left children
    
    /*
     * printf will also accept a format string an a bunch of values to
     * plug into the format string. %d is a placeholder for an integer
     *
     * never, ever allow the user to supply an un-sanitized format string
     */
    printf("%d ", curr->value);         // print me
    bintree_print_helper(curr -> right); // print right children
    return;
}