#ifndef BSTClass
#define BSTClass
#include <string>

using namespace std;

class BST
{
	private:
			struct Node
			{
				string letter;
				string code;
				Node *left;
				Node *right;
			};
			Node *root;

	public:
			BST()
			{
				root = NULL;
			}
			void Insert(Node *&r, string letter, string code)
			{
				if(r == NULL)
				{
					r = new Node; r->letter = letter;
					r->left = r->right = NULL; r->code = code;
				}
				if(r->letter > letter) Insert(r->left, letter, code);
				if(r->letter < letter) Insert(r->right, letter, code);
			}
			void Insert(string letter, string code){Insert(root, letter, code);}
			void DisplayPreOrder(Node *r)
			{
				if(r != NULL)
				{
					// (P)(LC)(RC)
					cout << r->letter << "\t";
					DisplayInOrder(r->left);
					DisplayInOrder(r->right);
				}
			}
			void DisplayInOrder(Node *r)
			{
				if(r != NULL)
				{
					// (LC)(P)(RC)
					DisplayInOrder(r->left);
					cout << r->letter << "\t";
					DisplayInOrder(r->right);
				}
			}
			// Overrides DisplayInOrder(Node * )
			void DisplayInOrder(){DisplayInOrder(root);}
			void DisplayPreOrder(){DisplayPreOrder(root);}
			void DisplayPostOrder(Node *r)
			{
				if(r != NULL)
				{
					// (LC)(P)(RC)
					DisplayPostOrder(r->left);
					DisplayPostOrder(r->right);
					cout << r->letter << "\t";
				}
			}
			void Encode(char x)
			{
				Node* r = SearchAndReturn(root, x);
				if(r != NULL) cout << r->code;
				else cout << "Error.";
			}
			void Decode(string x)
			{
				Node* r = SearchAndReturnString(root, x);
				if(r->code == x) cout << r->letter;
				else cout << r->code << " with x being " << x << endl; cout << "Error.";
			}
			Node* SearchAndReturn(Node *r, char x)
			{
				if(r != NULL)
				{
					if(r->letter[0] == x) {return r;}
					else if(r->letter[0] > x) {SearchAndReturn(r->left, x);}
					else {SearchAndReturn(r->right, x);}
				}
				else return NULL;
			}
			Node* SearchAndReturnString(Node *r, string x)
			{
				if(r != NULL)
				{
					if(r->code == x) {cout << r->code << " matches " << x << endl; return r;}
					else if(r->code > x) {SearchAndReturnString(r->left, x);}
					else {SearchAndReturnString(r->right, x);}
				}
				else return NULL;
			}
};
#endif