#include "BinarySearchTree.h"
#include <iostream>
#include "RuntimeException.h"
using namespace std;

BinaryNode *BinarySearchTree::findMin(BinaryNode *t) throw(EmptyTree)

{
if (t == NULL) throw EmptyTree();
while (t->left != NULL) t = t->left;
return t;
}


BinaryNode *BinarySearchTree::find(int x, BinaryNode *t) throw(ItemNotFound )

{
while (t != NULL)
if (x < t->key) t = t->left;
else if (x > t->key) t = t->right;
else return t; // found
throw ItemNotFound();
}
BinaryNode *BinarySearchTree::insert(int x,
BinaryNode *t) 
{
static long count=0;
count++;



if (t == NULL){ t = new BinaryNode(x,count);
count=0;
}
else if (x < t->key){
	t->left = insert(x, t->left);

}
else if (x > t->key){
	
t->right = insert(x, t->right);

}
else
throw DuplicateItem();
return t;
}
BinaryNode *BinarySearchTree::removeMin(BinaryNode *t) throw(ItemNotFound)
 // private function
{
if (t == NULL) throw ItemNotFound();
if (t->left != NULL)
t->left = removeMin(t->left);
else {
BinaryNode *node = t;
t = t->right;
traverse(t);
delete node;
}
return t;
}
void BinarySearchTree::traverse(BinaryNode *t) throw(ItemNotFound)
{

	if(t!=NULL){
		t->searchcost--;
		traverse(t->left);
		traverse(t->right);

	}
}

BinaryNode *BinarySearchTree::remove(int x, BinaryNode *t) throw(ItemNotFound)
 // private function
{ if (t == NULL) throw ItemNotFound();
if (x< t->key)
t->left = remove(x, t->left);
else if (x > t->key)
t->right = remove(x, t->right);
else if (t->left != NULL && t->right != NULL) {
// item x is found; t has two children
t->key = findMin(t->right)->key;
t->right = removeMin(t->right);
} else { //t has only one child

BinaryNode *node = t;
t= (t->left != NULL) ? t->left : t->right;

traverse(t);

delete node;
}
return t;
}
void BinarySearchTree::display(BinaryNode *t) const
{
	if(t)
	{
	display(t->left);
	cout<<t->key<<"["<<t->searchcost<<"] ";
	display(t->right);


	}


}
long BinarySearchTree::sum(BinaryNode *t) const
{
static long count=0;
long count2;
if(t)
	{
	sum(t->left);
	sum(t->right);
	count=count+(t->searchcost);
	if((t->searchcost)==1){
		count2=count;
		count=0;
		return count2;
	}
	}



}