#include<iostream>
using namespace std;

struct tree_node {
	tree_node *left = 0, *right = 0;
	string data;
};

bool add_to_tree(tree_node **root, string new_data){
	if(*root == NULL){
		*root = new tree_node;
		(*root)->data = new_data;
		return true;
	}
	tree_node *place = *root;
	while(1){
		if(place->data < new_data){
			if(!place->right){
				place->right = new tree_node;
				place->right->data = new_data;
				return true;
			}
			place = place->right;
		} else if(new_data < place->data){
			if(!place->left){
				place->left = new tree_node;
				place->left->data = new_data;
				return true;
			}
			place = place->left;
		} else { // They're equal
			return false; // It's already in the tree
		}
	}
}

void print_preorder(tree_node *place){
	if(place){
		cout << place->data << endl;
		print_preorder(place->left);
		print_preorder(place->right);
	}
}

bool is_in_tree_recursive(tree_node *place, string tofind){
	if(place){
		if(place->data == tofind)
			return true;
		if(place->data < tofind)
			return is_in_tree_recursive(place->right, tofind);
		return is_in_tree_recursive(place->left, tofind);
	}
	return false;
}

bool is_in_tree_iterative(tree_node *place, string tofind){
	while(place){
		if(place->data == tofind)
			return true;
		if(place->data < tofind)
			place = place->right;
		else
			place = place->left;
	}
	return false;
}

int main(){
	tree_node *root = 0;

	add_to_tree(&root, "Wallaby");
	add_to_tree(&root, "Zebra");
	cout << "Yak before we added it?  " << is_in_tree_iterative(root, "Yak") << endl;
	add_to_tree(&root, "Yak");
	add_to_tree(&root, "Bison");
	add_to_tree(&root, "Elephant");
	cout << "Yak after we added it?  " << is_in_tree_iterative(root, "Yak") << endl;
	print_preorder(root);
	cout << "Hippo?  " << is_in_tree_recursive(root, "Hippo") << endl;
	cout << "Bison?  " << is_in_tree_recursive(root, "Bison") << endl;

	return 0;
}