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

typedef struct s_node {
    int element;
    struct s_node* left;
    struct s_node* right;
} *Nodeptr, Node;

typedef Nodeptr* Tree;

Tree tree_create() {
    Tree t = malloc(sizeof( Nodeptr ));
    *t = NULL;
    return t;
}

void tree_add(Tree t, int element) {
    Nodeptr n = malloc(sizeof(Node));
    n->element = element;
    n->left = NULL;
    n->right = NULL;

    if(*t == NULL) {
        *t = n;
    } else {
        Nodeptr iter = *t;
        while(1) {
            if(iter->element > element) {
                if(iter->left == NULL) {
                    iter->left = n;
                    return;
                } else {
                    iter = iter->left;
                }
            } else if(iter->element < element) {
                if(iter->right == NULL) {
                    iter->right = n;
                    return;
                } else {
                    iter = iter->right;
                }
            } else {
                free(n);
                return;
            }
        }
    }
}

void tree_remove(Tree t, int element) {
    Nodeptr iter = *t;
    Nodeptr parent = NULL;
    while(iter != NULL) {
        if(iter->element > element) {
            parent = iter;
            iter = iter->left;
        } else if(iter->element < element) {
            parent = iter;
            iter = iter->right;
        } else {
            break;
        }
    }
    if(iter == NULL) return; // Not found

    if(iter->right == NULL) {
        if(parent == NULL)              *t = iter->left;
        else if(parent->left == iter)   parent->left = iter->left;
        else if(parent->right == iter)  parent->right = iter->left;
        else assert(0);
        free(iter);
    } else if(iter->left == NULL) {
        if(parent == NULL)              *t = iter->right;
        else if(parent->left == iter)   parent->left = iter->right;
        else if(parent->right == iter)  parent->right = iter->right;
        else assert(0);
        free(iter);
    } else {
        Nodeptr iter2, parent2;
        iter2 = iter->left;
        parent2 = NULL;
        while(iter2->right != NULL) {
            parent2 = iter2;
            iter2 = iter2->right;
        }
        if(parent2 == NULL) {
            iter->left = iter2->left;
        } else {
            parent2->right = iter2->left;
        }
        iter->element = iter2->element;
        free(iter2);
    }
}

int tree_contains(Tree t, int element) {
    Nodeptr iter = *t;
    while(iter != NULL) {
        if(iter->element > element) {
            iter = iter->left;
        } else if(iter->element < element) {
            iter = iter->right;
        } else {
            return 1;
        }
    }
    return 0;
}

void tree_print_node_rec(Nodeptr n, int level) {
    if(n == NULL) return;

    tree_print_node_rec(n->right,level+1);

    for(int i = 0; i < level; i++) printf("\t");
    printf("%d\n", n->element);

    tree_print_node_rec(n->left, level+1);
}

void tree_print(Tree t) {
    tree_print_node_rec(*t, 0);
    printf("----------\n");
}

void tree_nodefree_rec(Nodeptr n) {
    if(n == NULL) return;
    tree_nodefree_rec(n->left);
    tree_nodefree_rec(n->right);
    free(n);
}

void tree_free(Tree t) {
    tree_nodefree_rec(*t);
    free(t);
}

int main( int argc, char *argv[] ) {
    int data[10] = {5,7,2,8,6,4,3,1,9,0};
    Tree t = tree_create();
    for(int i = 0; i < 10; i++) {
        tree_add(t,data[i]);
    }
    tree_print(t);
    for(int i = 0; i < 10; i++) {
        assert(tree_contains(t,data[i]));
    }
    for(int i = 0; i < 5; i++) {
        tree_remove(t,data[i]);
    }
    tree_print(t);
    for(int i = 5; i < 10; i++) {
        assert(tree_contains(t,data[i]));
    }
    tree_free(t);
    return 0;
}