#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

bool search1(tree *t, datatype d) {
	if (t == empty_tree)
		return false;
	else if (t->data == d)
		return true;
	else if (d<t->data) 
		return search1(t->left, d);
	else
		return search1(t->right, d);
}

tree *search2(tree *t, datatype d) {
	if (t == empty_tree)
		return empty_tree;
	else if (t->data == d)
		return t;
	else if (d<t->data) 
		return search2(t->left, d);
	else
		return search2(t->right, d);
}

void print1(tree *t) {
	if (t == empty_tree) {
	} else {
		print1(t->left);
		printf("%d\n", t->data);
		print1(t->right);
	}
}

tree *searchParent(tree *t, tree *parent, datatype d) {
	if (t == empty_tree)
		return parent;
	else if (t->data == d)
		return empty_tree;
	else if (d<t->data) 
		return searchParent(t->left, t, d);
	else
		return searchParent(t->right, t, d);
}

void insert(tree *t, datatype d) {
	tree *s, *r;

	if (t == empty_tree) {
		r = (tree *)malloc(sizeof(tree));
		t->data = d;
		t->left = empty_tree;
		t->right = empty_tree;
		*t = *r;
	} else {
		s = searchParent(t, empty_tree, d);
		if (s != empty_tree) {
			r = (tree *)malloc(sizeof(tree));
			r->data = d;
			r->left = empty_tree;
			r->right = empty_tree;
			if (d<s->data) 
				s->left = r;
			else
				s->right = r;
		}
	}
}