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

#include "binary_search_tree.h"
#include "print_ascii_tree.h"

SearchTree make_empty(SearchTree t)
{
    if(t != NULL) {
        make_empty(t->left);
        make_empty(t->right);
        free(t);
    }

    return NULL;
}

/**
 *  find x or return NULL.
 */
Position find(elem_t x, SearchTree t)
{
    if(t != NULL) {
        if(t->elem == x) return t;
        else if(t->elem > x) return find(x, t->right);
        else return find(x, t->left);
    }

    return NULL;
}

Position find_min(SearchTree t)
{
    if(t == NULL)
        return NULL;
    else if(t->left == NULL)
        return t;
    else
        return find_min(t->left);
}

Position find_max(SearchTree t)
{
    if(t == NULL)
        return NULL;
    else if(t->right == NULL)
        return t;
    else
        return find_max(t->right);
}

SearchTree insert(elem_t x, SearchTree t)
{
    if(t == NULL) {
        t = malloc(sizeof(struct TreeNode));
        t->elem = x;
        t->left = NULL;
        t->right = NULL;
    } else if(x > t->elem)
        t->right = insert(x, t->right);
    else if(x < t->elem)
        t->left = insert(x, t->left);
    /* The t->elem = x need do nothing, already inserted */

    return t;
}

SearchTree delete(elem_t x, SearchTree t)
{
    Position p, tmp;

    p = find(x, t);

    if(p == NULL) {
        /* elem x not found */
        printf("x not found!(do nothing)\n");
    } else if(p->left == NULL && p->right == NULL) {
        free(p);
    } else if(p->left == NULL) {
        tmp = p;
        p = p->right;
        free(tmp);
    } else if(p->right == NULL) {
        tmp = p;
        p = p->left;
        free(tmp);
    } else {
        /* replace and delete */
        tmp = find_min(p->right);
        p->elem = tmp->elem;
        t->right = delete(p->elem, t->right);
    }

    return t;
}

elem_t retrieve(Position p)
{

}

void print_tree_pre_order(SearchTree t)
{
    if(t == NULL)
        return;
    print_tree_pre_order(t->left);
    printf("%d ", t->elem);
    print_tree_pre_order(t->right);
}

void test()
{
    SearchTree t = NULL;
    t = make_empty(t);
    t = insert(1, t);
    insert(4, t);
    insert(3, t);
    insert(2, t);
    insert(10, t);
    insert(12, t);
    insert(-1, t);

    print_tree_pre_order(t);
    printf("\n");
    print_ascii_tree(t);
}

int main()
{
    test();
    return 0;
}