#include "util.h"
#include <string.h>
#include <stdio.h>

typedef struct tree *T_tree;
struct tree {
	T_tree left;
	string key;
	T_tree right;
};
T_tree Tree(T_tree l, string k, T_tree r)
{
	T_tree t = checked_malloc(sizeof(*t));
	t->left = l;
	t->key = k;
	t->right = r;
	return t;
}

T_tree insert(string key, T_tree t)
{
	if (t == NULL)
		return Tree(NULL, key, NULL);
	else if (strcmp(key, t->key) < 0)
		return Tree(insert(key, t->left), t->key, t->right);
	else if (strcmp(key, t->key) > 0)
		return Tree(t->left, t->key, insert(key, t->right));
	else
		return Tree(t->left, key, t->right);
}

bool member(string key, T_tree t)
{
	if (t == NULL) {
		return FALSE;
	}

	if (strcmp(t->key, key) == 0) {
		return TRUE;
	}

	return member(key, t->left) || member(key, t->right);
}

int main(int argc, char *argv[])
{
	string values[] = { "t", "s", "p", "i", "p", "f", "b", "s", "t" };

	T_tree tree;

	for (int i = 0; i < 9; i++) {
		tree = insert(values[i], tree);
	}

	printf("member: %d\n", member("t", tree));
}