// Creates an empty binary tree
template<class T> binary_tree<T>::binary_tree() {

}

// Cleans up memory before the tree's destruction
template<class T> binary_tree<T>::~binary_tree() {
	destruct(root);
}

// Inserts the value into the appropriate place in the tree.
template<class T> void binary_tree<T>::insert(T val) {
	insert(val,root);
}

// Helper function for insert that takes a node argument.
template<class T> void binary_tree<T>::insert(T val, node* n) {
	if (n == 0) {
		root = new node(val,0,0);
	} else {
		if (val >= n->val) {
			if (n->right == 0) {
				n->right = new node(val,0,0);
			} else {
				insert(val,n->right);
			}
		} else {
			if (n->left == 0) {
				n->left = new node(val,0,0);
			} else {
				insert(val,n->left);
			}
		}
	}
}

// Finds the v in the tree such that v == val.  It's assumed that
// for the generic type being used that if both v < val and v > val
// are false, then v == val is true.  Once v is found, it is returned.
// If no matching value is found in the tree, not_found is thrown.
template<class T> T binary_tree<T>::find(T val) const {
	if (find(val,root) == val) {
		return val;
	} else {
		throw not_found();
	}
}

// Helper function for find that accepts a node argument.
template<class T> T binary_tree<T>::find(T val, node* n) const {
	if (n == 0) {
		throw not_found();
	} else {
		if (val == n->val) {
			return val;
		} else {
			if (val < n->val) {
				return find(val,n->left);
			} else {
				return find(val,n->right);
			}
		}
	}
}

// Removes a value from the tree.  Works identially to find (and operates
// with the same assumptions), except that it removes the value from the
// tree in addition to returning it.
template<class T> T binary_tree<T>::remove(T val) {
	return remove(val,root,root);
}

// Helper function to remove that accepts a node argument.
template<class T> T binary_tree<T>::remove(T val, node* n, node* parent) {
	if (val == parent->val) {
		n = parent->right;
		while (n->left != 0) {
			n = n->left;
		}
		n->left = parent->left;
	} else {
		if (val >= parent->val) {
			remove(val,parent->right,parent->right);
		} else {
			remove(val,parent->left,parent->left);
		}
	}

	return val;
}

// Helper function for the destructor that recursively deletes all
// nodes in the tree.
template<class T> void binary_tree<T>::destruct(node* n) {
	if (n != 0) {
		if (n->left != 0) {
			destruct(n->left);
		}
		if (n->right != 0) {
			destruct(n->right);
		}
		delete n;
	}
}