#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;
} 

void Tree::DeleteNode(treenode * &tree)
{
	int value;
	bool found;
	treenode * tempPtr;
	tempPtr = tree;
	if(tree->leftPtr = 0)
	{
		tree = tree->rightPtr;
		delete tempPtr;
	}
	else if (tree->rightPtr == 0)
	{
		tree = tree->leftPtr;
		delete tempPtr;
	}
	else
	{
		GetPredecessor(tree->leftPtr, value);
		tree->data = value;
		Delete(tree->leftPtr, value, found);
		if(!found)
		{
			cout << "error in delete after getpredecesor" << endl;
		}
	}
}

void Tree::GetPredecessor(treenode * tree, int &value)
{
	while(tree->rightPtr != 0)
	{
		tree = tree->rightPtr;
	}
	value = tree->data;

}

void Tree::Delete(treenode * &tree, int item, bool &found)
{

	if(tree == 0)
	{
		found = false;
		return;
	}
	if(item < tree->data)
	{
		Delete(tree->leftPtr, item, found);
	}
	else if(item > tree->data)
	{
		Delete(tree->rightPtr, item, found);
	}
	else
	{
		found = true;
		DeleteNode(tree);
	}
}