// ******************************
// ***                        ***
// ***   YOUR CODE HERE !!!   ***
// ***                        ***
// ******************************

//---------------------------------------------------------------
//---------------------------------------------------------------

void Print_Menu (void)
{
	cout << "MENU" << endl;
	cout << "  1. Add item" << endl;
	cout << "  2. Search for an item" << endl;
	cout << "  3. Display items in order" << endl;
	cout << "  4. Display items breadth-first" << endl;
	cout << "  5. QUIT" << endl << endl;
}

//---------------------------------------------------------------

int Read_Choice (void)
{
	int c;

	do {
		cout << "Choice: ";
		cin >> c;
	} while ((c < 1) || (c > 5));

	return c;
}

//---------------------------------------------------------------

void Process_Choice(int c, BST<int> &tree)
{
	int v;

	switch (c)
	{
	case 1 :
		cout << "Value to insert: ";
		cin >> v;
		tree.Insert(v);
		break;
	case 2 :
		cout << "Value to find: ";
		cin >> v;
		if(tree.Search(v) != NULL)
			cout << v << " is in the tree" << endl;
		else
			cout << v << " is not in the tree" << endl;
		break;
	case 3 :
		tree.Traverse();
		break;
	case 4 :
		tree.Breadth_Traverse();
		break;
	}
}

//---------------------------------------------------------------

void main(void)
{
	int choice;
	BST<int> tree;

	do {
		Print_Menu();
		choice = Read_Choice();
		Process_Choice(choice, tree);
	} while (choice != 5);

	system("pause");
}