#include<iostream>
#include<stack>
using namespace std;
class node
{
public:
string item; //data item
double cost; //data item
node *pleft;
node *pright;
node *pparent;
//ptr to next node in list

node(string s, double c)  //constructor
{ //to insert data
item=s;
cost=c;
pleft=NULL;
pright=NULL;
}
void displaynode()
{
cout << "{" << item << ", " << cost << "} ";
}
};
class Tree
{
private:
node* proot; //ptr to first node on list
public:
Tree()  //constructor
{
proot = NULL;
 } //(no nodes on list yet)
//insert at start of list

int insertFirst(string i, double c)
{
node* pNewnode = new node(i, c); //creates new node

if(proot==NULL)
proot = pNewnode;
else
{
    node *pcurrent=proot;
    node *pparent;
    while(1)//loop through tree
	{
	pparent=pcurrent;//remember where you have come from
	if(i<pcurrent->item)//which direction
	{
		pcurrent=pcurrent->pleft;
		if(pcurrent==NULL)
		{

		pparent->pleft=pNewnode;
		return 0;
		}
	}
		else
		{
			pcurrent=pcurrent->pright;
		if(pcurrent==NULL)
		{

		pparent->pright=pNewnode;
		return 0;
		}
		}
	}
}
}

void display()
 {
 stack<node*> globalStack;
globalStack.push(proot);
int nBlanks = 32;
bool isRowEmpty = false;
cout <<
"......................................................";
cout << endl;
while(isRowEmpty==false)
{
stack<node*> localStack;
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
cout << ' ';
while(globalStack.empty()==false)
{
node* temp = globalStack.top();
globalStack.pop();
if(temp != NULL)
{
cout << temp->item;
localStack.push(temp->pleft);
localStack.push(temp->pright);
if(temp->pleft != NULL ||
temp->pright != NULL)
isRowEmpty = false;
}
else
{
cout << "--";
localStack.push(NULL);
localStack.push(NULL);
}
for(int j=0; j<nBlanks*2-2; j++)
cout << ' ';
} //end while globalStack not empty
cout << endl;
nBlanks /= 2;
while(localStack.empty()==false)
{
globalStack.push( localStack.top() );
localStack.pop();
}
} //end while isRowEmpty is false
cout <<
"......................................................";
cout << endl;

 }

int find(string key) //find link with given key
{ //(assumes non-empty list)
	node* pcurrent = proot; //start at ‘first’
	while(pcurrent->item != key) //while no match,
	{if(pcurrent == NULL) //if end of list,
	{cout<<"Not Found"<<endl;
	return 0;
	}
	else if (pcurrent->item <key)
	{
	pcurrent = pcurrent->pright;
	}
	else
	{
		pcurrent=pcurrent->pleft;
	}
	}
	cout<<"Found "<<key<<endl;
	return 0; //found it
}
void inorder(node*pLocalRoot)
{
	if(pLocalRoot !=NULL)
	{
		inorder(pLocalRoot->pleft);
		pLocalRoot->displaynode();
		inorder(pLocalRoot->pright);
	}
}

void traverse()
{
	Tree x;
	x.inorder(proot);
}

void findmin()
{
node* pcurrent= proot;
	while(pcurrent->pleft != NULL)

	{
	pcurrent=pcurrent->pleft;
	}

pcurrent->displaynode();
}
void findmax()
{
	node*pcurrent=proot;
	while(pcurrent->pright !=NULL)
	{
		pcurrent=pcurrent->pright;
	}
	pcurrent->displaynode();
}
}; //end class node
int main()
{
Tree thetree; //make new list
thetree.insertFirst("Milk", 50.00);
thetree.insertFirst("Bread", 70.00);
thetree.insertFirst("Sugar", 150.00);
thetree.insertFirst("Salt", 10.00);
thetree.insertFirst("Yam", 50.00);
thetree.insertFirst("Crisps", 70.00);
thetree.insertFirst("Apples", 70.00);



thetree.display();

thetree.find("Crisps");
thetree.findmin();
thetree.traverse();
thetree.findmax();
return 0;
} //end main()