#ifndef _BSTREE_H_ // sentry
#define _BSTREE_H_

#include <string>
using namespace std;

class BinarySearchTree; // forward declaration

class BinarySearchNode
{
protected:
	string data;
	BinarySearchNode * left;
	BinarySearchNode * right;

public:
	BinarySearchNode(string data);
	virtual ~BinarySearchNode() { ; }
	virtual void print();

	friend class BinarySearchTree;
	friend class AVLTree; // XXX: fix this next time
};

class BinarySearchTree
{
public:
	BinarySearchTree(); // construtor
	~BinarySearchTree(); // destructor

	// operations
	bool is_empty();
	int get_size();
	bool exists(string val);
	void insert(string val);
	void clear(); // remove all nodes in tree

	// various ways to display
	void preorder_print();
	void inorder_print();
	void postorder_print();
	void print_tree();

private:

	// internal use functions
	void insert(BinarySearchNode * node);
	void delete_subtree(BinarySearchNode * node);
	void print_subtree(BinarySearchNode * node, int level);

	void preorder_print(BinarySearchNode * node);
	void inorder_print(BinarySearchNode * node);
	void postorder_print(BinarySearchNode * node);

protected:
	// the following have to be protected because we use them in the AVLTree
	BinarySearchNode * root;
	int size;

	// the get_height "triumverate"
public:     int get_height();
protected:  int get_height(BinarySearchNode * node);
private:   void get_height(BinarySearchNode * node, int height);
	       int max_height; // "temp" variable used in private get_height() func


public:
	// HOMEWORK:
	//bool del(string del_me);
};

#endif