#include "stringtree.h"

StringTree::StringTree()
{
	root = NULL;
}

void StringTree::insert(string s)
{
	Treenode* newnode = new Treenode(s);
	if (root == NULL)
		root = newnode;
	else
		insertintosubtree(root, newnode);
}

void StringTree::insertintosubtree(Treenode* subroot, Treenode* newnode)
{
	if (newnode->data < subroot->data)
	{
		// insert on left
		if (subroot->left == NULL)
			subroot->left = newnode;
		else
			insertintosubtree(subroot->left, newnode);
	}
	else if (newnode->data > subroot->data)
	{
		// insert on right
		if (subroot->right == NULL)
			subroot->right = newnode;
		else
			insertintosubtree(subroot->right, newnode);

	}
}

void StringTree::remove(string s)
{
	// what if tree is empty?
	if (root != NULL)
		root = removetreenode(root, s);
}

Treenode* StringTree::removetreenode(Treenode* subroot, string s)
{
	Treenode* forreturn;

	if (subroot != NULL)
	{
		if (subroot->data == s)
		{
			// remove this node!
			if (subroot->left == NULL)
				forreturn = subroot->right;
			// there is a left child
			else if (subroot->right == NULL)
				forreturn = subroot->left;
			// there are two children
			else
			{
				// go left, right, right ... until we find NULL
				Treenode* temp = subroot->left;
				while(temp->right != NULL)
					temp = temp->right;
				// replace that NULL with our right child
				temp->right = subroot->right;
				forreturn = subroot->left;
			}
			delete subroot;
			return forreturn;
		}
		else if (s < subroot->data)
			subroot->left = removetreenode(subroot->left, s);
		else
			subroot->right = removetreenode(subroot->right, s);
	}
	return subroot;
	// what if the node to remove only has one child?	
}

void StringTree::print()
{
	if (root == NULL)
		cout << "Empty Tree" << endl;
	else
		printsubtree(root, 0);
}

void StringTree::printsubtree(Treenode* subroot, int level)
{
	if (subroot != NULL)
	{
		printsubtree(subroot->right, level + 1);
		for (int i = 0; i < level; i++)
			cout << "  ";
		cout << subroot->data << endl;
		printsubtree(subroot->left, level + 1);
	}
}

int main()
{
	StringTree tree;

	//tree.insert("Hello");
	//tree.insert("Goodbye");
	//tree.insert("You say...");
	//tree.insert("I say...");
	//tree.insert("The teacher is an obvious baby-boomer");

	string userinput = "";

	while (userinput != "quit")
	{
		cin >> userinput;
		if (userinput == "insert")
		{
			cin >> userinput;
			tree.insert(userinput);
		}
		else if (userinput == "remove")
		{
			cin >> userinput;
			tree.remove(userinput);
		}

		cin.ignore(INT_MAX, '\n');
		tree.print();
	}

	return 0;
}