/* Simple BST program (with included comments below)
*
* Wyatt Carss
* February 24th, 2011
*
* Reads in numbers until EOF, then prints them out as a tree. Stores them
* in a binary search tree. Numbers must be sorted, or operation is undefined.
*/

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

/* Just a simple tree type */
typedef struct tree_t
{
    struct tree_t *left;
    struct tree_t *right;
    double data;
}Tree;


Tree *make_bst(double *arr, int low, int high);
void print_tree(Tree *t, int depth);
void destroy(Tree *t);


/* Reads from stdin until eof - prints a list of ints as an inorder bst */
int main()
{
    int size = 1, i = 0;
    double *arr = malloc(sizeof(double) * size);
    double input = 0;
    Tree *t = NULL;

    while(!feof(stdin) && input != -9991)
    {
        if(1 != fscanf(stdin, "%lf", &input))
        {
            if(feof(stdin)) break;
            /*printf(" couldn't read that one, sorry!\n");*/
        }

        arr[i] = input;
        i++;
        if(i >= size)
        {
            size *= 2;
            arr = realloc(arr, size*sizeof(double));
        }
    }

    /* printf("size is %d\n", sizeof(arr)/sizeof(int)-1); */
    t = make_bst(arr, 0, i-1);
    print_tree(t, 0);

    destroy(t);
    free(arr);
    return 0;
}

/* recursively frees nodes, necessarily post-order */
void destroy(Tree *t)
{
    if(t != NULL)
    {
        destroy(t->left);
        destroy(t->right);
        free(t);
    }
}

/* prints in-order, uses depth to determine tab-formatting */
void print_tree(Tree *t, int depth)
{
    int i;

    if(t != NULL)
    {
        print_tree(t->right, depth+1);

        /* depth is 0 on first call */
        for(i = 0; i < depth; i++) printf("\t");

        printf("%g\n", t->data);
        print_tree(t->left, depth+1);
    }
}

/* Recursively creates a balanced search tree, given a sorted arr of doubles */
Tree *make_bst(double *arr, int low, int high)
{
    Tree *t = NULL;

    /* If the array is empty, just NULL and get out */
    if(arr == NULL || low > high)
    {
        t = NULL;
    }
    else
    {
        /* otherwise, allocate a new node */
        t = malloc(sizeof(Tree));

        /* if we have 1 element, save it and leave */
        if(low == high)
        {
            t->data = arr[low];
            t->left = NULL;
            t->right = NULL;
        }
        else if(high-low == 1)
        {
            /* if we have 2 elements, always assign the greater
                to the root, and the lesser to the left */
            t->data = arr[high];
            t->left = malloc(sizeof(Tree));
            t->right = NULL;
            t->left->data = arr[low];
            t->left->left = NULL;
            t->left->right = NULL;
        }
        else
        {  
            /* Any higher number, reduce the bounds and recurse */
            t->data = arr[(low+high)/2];
            t->left = make_bst(arr, low, (low+high)/2-1);
            t->right = make_bst(arr, (low+high)/2+1, high);
        }
    }

    return t;
}

/*
Alright, Im done. Its commented, operates properly on a user-inputted list of 
doubles instead of ints, runs until EOF, valgrind says its clean, and it isnt 
horrifically formatted.

This entire file is also hosted at: http://wcarss.ca/bst_tree.txt and
http://wcarss.ca/bst_tree.c - it does compile and operate as specified.

Took me a few minutes of thought to remember that the proper way to write BST 
code is by analyzing all of the base cases. Once I recalled that, it came back 
fluidly, and Ive got clearly defined "no elements", "1 element", "2 elements" 
and "all other elements" blocks. The bugs that were previously in the program 
were entirely down to not covering the cases correctly.

Fun problem. :) .. But, the second interviewer never called .. ?

Thanks,
-Wyatt
*/

/*old note: took me a few minutes, but it compiles and operates properly; also
 prints out in-order and correctly frees. Now it takes in input from stdin 
 until the user provides an EOF.*/

/* old program: (probably doesnt even compile :P)

typedef struct Tree
{
 struct Tree *left;
 struct Tree *right;
 int data;
}Tree;

int main()
{

int arr[] = {1, 2, 3, 4, 5, 6};

int arr2[] = {1, 2};
    Tree *t = make_bst(arr, 0, 5);

    return 0;
}

Tree *make_bst(int *arr, int low, int high)
{
    Tree *t = NULL;

    if(arr == NULL || low > high)
    {
        t = NULL;
    }
    else if(low == high)
    {
       t->data = low;
       t->left = NULL;
       t->right = NULL;
    }
    else
    {   

t = malloc(sizeof(Tree));

    t->data = arr[(low+high)/2];
          t->left = make_bst(arr, low, (low+high)/2-1);
        t->right = make_bst(arr, (low+high)/2+1, high);
    }
    return t;
} */