struct treenode {
	treenode *leftPtr;
	int dadta;
	treenode *rightPtr;
};
class Tree {
public:
	Tree();
	~Tree();
	void insertNode( treenode *&, const int&);
	void preOrderTraversal(treenode *);
	void inOrderTraversal(treenode *);
	void postOrderTraversal(treenode *);
	void findNode(treenode *, int ,treenode* , treenode *&, treenode *&);
	void deleteItem(int value);
	treenode*& Root() {return rootPtr;}
private:
	treenode *rootPtr;
	void DeleteHelper(treenode *);
	void DeleteNode(treenode *&);
	void Delete(treenode * & tree, int data, bool & found);
	void GetPredecessor(treenode *, int &);
};

#include <iostream>
using namespace std;
#include "tree.h"
#include <assert.h>
Tree::Tree() { rootPtr=0; }

void Tree::insertNode(treenode * &ptr, const int &value)
{
	if(ptr==0){
		ptr=new treenode;
		assert( ptr !=0);
		ptr->data=value;
		ptr->leftPtr=0;
		ptr->rightPtr=0;
	}
	else
		if( value < ptr->data)
			insertNode( ptr->leftPtr, value);
		else
			if( value  > ptr->data)
				insertNode( ptr->rightPtr, value);
			else
				cout << value << " dup " << endl;
}

void Tree::preOrderTraversal(treenode* ptr)
{
	if(ptr !=0){
		cout << ptr->data << " ";
		preOrderTraversal(ptr->leftPtr);
		preOrderTraversal(ptr->rightPtr);
	}
}

void Tree:inOrderTraversal( treenode * ptr)
{
	if (ptr !=0){
		inOrderTraversal(ptr->leftPtr);
		cout << ptr->data << " ";
		inOrderTraversal(ptr->rightPtr);
	}
}

void Tree:postOrderTraversal(treenode * ptr)
{
	if( ptr !=0){
		postOrderTraversal(ptr->leftPtr);
		postOrderTraversal(ptr->rightPtr);
		cout << ptr->data << " ";
	}
}
Tree::~Tree()
{
	cout << " entering destructor\n";
	DeleteHelper(rootPtr);
}

void Tree::DeleteHelper(treenode * ptr)
{
	if(ptr !=0){
		DeleteHelper(ptr->leftPtr);
		DeleteHelper(ptr->rightPtr);
		cout << " deleting: "<< ptr->data << endl;
		delete ptr;
	}
}
void Tree::findNode(treenode * ptr, int value,treenode* priorPtr, treenode *& nodePtr, treenode *& parentPtr)
{
	if(ptr==0){
		nodePtr=0;
		parentPtr=priorPtr;
		//we have found where it goes but it isn't there
	}
	else
		if( value  < ptr->data)
			findNode( ptr->leftPtr, value, ptr, nodePtr, parentPtr);
		else
			if( value > ptr->data)
				findNode( ptr->rightPtr, value, ptr, nodePtr, parentPtr);
			else
			{
				nodePtr=ptr;
				parentPtr=priorPtr;
			}
}
void Tree::deleteItem(int value)
{
	bool found;
	Delete(rootPtr, value, found);
	if(!found)
		cout << value << " was not found " << endl;
}