/*
 * bst.c
 *
 * Computer Science 50, Fall 2011
 * section7
 *
 * Credit: Tommy MacWilliam (aka TMac)
 *
 * Demos a binary search tree.
 */

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

// typedef a node
typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

// function prototypes
node *create_node(int value);
void insert(int value, node *parent);
int lookup(int value, node *parent);
int sum(node *parent);

int
main(void)
{
    // create a root node
    node *root = create_node(8);
    
    // build out the rest of the tree
    insert(3, root);
    insert(10, root);
    insert(1, root);
    insert(6, root);
    insert(14, root);
    insert(4, root);
    insert(7, root);
    insert(13, root);

    printf("Let's see...\n");
    printf("Found a 5? %d\nFound a 7? %d\nFound a 10? %d\n",
           lookup(5, root), lookup(7, root), lookup(10, root));
    
    printf("Sum of all nodes: %d\n", sum(root));
    
    // success!
    return 0;
}

/*
 * Creates a new node with the given value.
 */
node*
create_node(int value)
{
    node *new = malloc(sizeof(node));
    new->value = value;
    new->left = NULL;
    new->right = NULL;
    return new;
}

/*
 * Inserts a new node.
 * (Quick Quiz: how fast is this, asymptotically?)
 */
void
insert(int value, node *parent)
{
    // don't allow duplicates
    if(value == parent->value)
        return;
        
    else if(value < parent->value)
    {
        // if a child, recurse into the left subtree
        if (parent->left != NULL)
            insert(value, parent->left);

        // if no child, insert a new node as left child
        else 
            parent->left = create_node(value);
    }
    
    else if(value > parent->value)
    {
        // if a child, recurse into the right subtree
        if (parent->right != NULL)
            insert(value, parent->right);

        // if no child, insert a new node as right child        
        else
            parent->right = create_node(value);
    }
}

/*
 * Searches the tree for a given value.
 * (Quick Quiz: how fast is this, asymptotically?)
 */
int
lookup(int value, node *parent)
{
    // the value is not found in the tree
    if (parent == NULL)
        return 0;

    // the value is found in the tree
    else if (value == parent->value)
        return 1;

    // if the value is smaller than the parent, go into the left subtree
    else if (value < parent->value)
        return lookup(value, parent->left);
    
    // it the value is larger than the parent, go into the right subtree
    else
        return lookup(value, parent->right);
}

/*
 * Sums the nodes of the tree.
 */
int
sum(node *parent)
{
    // TODO
    return 0;
}