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

/* use integers as datatype, but this could be anything */
typedef int datatype;


/* actual definition of a binary tree type */
typedef struct tree {
    datatype data;
    struct tree *left;
    struct tree *right;
} tree;

/* useful short-hand */
#define empty_tree (tree *)NULL







/* binary search 1 */
bool search1(tree *t, datatype d) {
    if (t==empty_tree) /* empty case */
        return false;
    else {
        if (t->data == d) /* found it */
            return true;
        else if (d < t->data ) /* search correct branch */
            return search1(t->left, d);
        else /* d > t->data */
            return search1(t->right, d);
    }
}

/* binary search 2 */
bool search2(tree *t, datatype d) {
    return t==empty_tree ? false : /* empty case */
        (t->data == d ? true : /* found it */
        /* else search correct branch */
        search2( (d < t->data ? t->left : t->right), d ) );
}

/* printing 1 */
void print1(tree *t) {
    if (t!=empty_tree) {
        print1(t->left);
        printf("%d ", t->data);
        print1(t->right);
    }
}

/* generic (infix) depth first traverse */
void depth_first_traverse(tree *t, void (*f)(datatype)) {
    if (t!=empty_tree) {
        depth_first_traverse(t->left,f); 
        f(t->data); 
        depth_first_traverse(t->right,f);
    }
}

void print_data(datatype d) {
    printf("%d ", d);
}

void print3(tree *t) {
    depth_first_traverse(t, print_data);
}

/* insert 1 */
void insert1(tree *t, datatype d) {
    if (t==empty_tree) { /* empty case */
        t = (tree *)malloc(sizeof(tree));
        if (t!=empty_tree) { /* ack! */
            t->data = d;
            t->left = empty_tree;
            t->right = empty_tree;
        } /* silently do nothing... */
    } else {
        if (t->data == d) {/* found it */
            /* do nothing ! */
        } else if (d < t->data ) /* insert in correct branch */
            return insert1(t->left, d);
        else /* d > t->data */
            return insert1(t->right, d);
    }
}

/* insert 2 */
void traverse2(tree *t, datatype d, void (*action)(tree *,datatype)) {
    if (t==empty_tree) { /* empty case */
        action(t, d);
    } else {
        if (t->data == d) {/* found it */
            /* do nothing ! */
        } else if (d < t->data ) /* insert in correct branch */
            return insert1(t->left, d);
        else /* d > t->data */
            return insert1(t->right, d);
    }
}

void create_node(tree *t, datatype d) {
    t = (tree *)malloc(sizeof(tree));
    if (t != empty_tree) { /* ack! */
        t->data = d;
        t->left = empty_tree;
        t->right = empty_tree;
    }
}

void insert2(tree *t, datatype d) {
    traverse2(t, d, create_node);
}