/* search_tree.h */

#ifndef _SEARCH_TREE_H
#define _SEARCH_TREE_H

struct tree_node;
typedef struct tree_node *position;
typedef struct tree_node *search_tree;

search_tree make_empty(search_tree t);
position find(int x, search_tree t);
position find_min(search_tree t);
position find_max(search_tree t);
search_tree insert_tree(int x, search_tree t);
search_tree delete_tree(int x, search_tree t);
int retrieve(position p);
void print_search_tree(search_tree t);

#endif

/* search_tree.c */

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

struct tree_node
{
    int element;
    search_tree left;
    search_tree right;
};

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

position find(int x, search_tree t)
{
    if(t == NULL)
    {
        return NULL;
    }
    if(x < t->element)
        return find(x, t->left);
    else if(x > t->element)
        return find(x, t->right);
    else
        return t;
}

position 
find_min(search_tree t)
{
    if(t == NULL)
        return NULL;
    else if(t->left == NULL)
        return t;
    else
        return find_min(t->left);
}

position 
find_max(search_tree t)
{
    if(t == NULL)
        return NULL;
    else if(t->right == NULL)
        return t;
    else
        return find_max(t->right);
}

search_tree 
insert_tree(int x, search_tree t)
{
    if(t == NULL)
    {
        /* create and return a one-node tree */
        t = malloc(sizeof(struct tree_node));
        if(t == NULL)
        {
            printf("out of space!!!\n");    
            exit(1);
        }
        else
        {
            t->element = x;
            t->left = NULL;
            t->right = NULL;
        }
    }
    else if(x < t->element)
        t->left = insert_tree(x, t->left);
    else if(x > t->element)
        t->right = insert_tree(x, t->right);;
    /* else x is in the tree already; we‘ll do nothing */

    return t;    /* do not forget this line */
}

search_tree 
delete_tree(int x, search_tree t)
{
    position tmpcell;

    if(t == NULL)
    {
        printf("element not found!\n");
        exit(1);
    }    
    else if(x < t->element)    /* go left */
        t->left = delete_tree(x, t->left);
    else if(x > t->element)    /* go right */
        t->right = delete_tree(x, t->right);
    else if(t->left && t->right)    /* two children */
    {
        /* replace with smallest in right subtree */
        tmpcell = find_min(t->right);
        t->element = tmpcell->element;
        t->right = delete_tree(t->element, t->right);
    }
    else    /* one or zero children */
    {
        tmpcell = t;
        if(t->left == NULL)    /* also  handles 0 children */
            t = t->right;
        else if(t->right == NULL)
            t = t->left;
        free(tmpcell);
    }
    return t;
}

int 
retrieve(position p)
{
    return p->element;
}

void
print_search_tree(search_tree t)
{
    if(t == NULL)
        ;
    else if(t->left == NULL && t->right == NULL)
        printf("%d\n", t->element);
    else
    {
        printf("%d\n", t->element);
        print_search_tree(t->left);
        print_search_tree(t->right);
    }
}

/* search_tree_test.c */

#include "search_tree.h"
#include <stdio.h>

int 
main(void)
{
    search_tree t = NULL;
    position pmin, pmax;
    int min, max;

    t = make_empty(t);
    printf("insert 5 to search_tree\n");
    t = insert_tree(5, t);
    printf("insert 4 to search_tree\n");
    t = insert_tree(4, t);
    printf("insert 2 to search_tree\n");
    t = insert_tree(2, t);
    printf("insert 6 to search_tree\n");
    t = insert_tree(6, t);
    printf("insert 8 to search_tree\n");
    t = insert_tree(8, t);

    pmin = find_min(t);
    pmax = find_max(t);
    
    min = retrieve(pmin);
    max = retrieve(pmax);

    printf("the search tree is :\n");
    print_search_tree(t);
    printf("min = %d\nmax = %d\n", min, max);

    printf("\n");
    printf("delete 2 from search_tree\n");
    t = delete_tree(2, t);
    printf("the search_tree is :\n");
    print_search_tree(t);
}