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

// Driver

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

void main()
{
	Tree intTree;
	int intVal;
	int values[100];
	int count = 0;
	treenode * &root = intTree.Root();
	treenode *priorPtr = 0, *nodePtr = 0, *parentPtr = 0;

	cout << "enter integers (ctrl-z to end): ";
	while(cin >> intVal)
	{
		values[count++] = intVal;
		intTree.insertNode(root, intVal);
	}
	cout << "\nPreorder Traversal: ";
	intTree.preOrderTraversal(root);

	cout << "\nInOrder Traversal: ";
	intTree.inOrderTraversal(root);

	cout << "\nPostOrder Traversal: ";
	intTree.postOrderTraversal(root);

	cout << endl;

	intTree.findNode(root, 4, priorPtr, nodePtr, parentPtr);

	if(nodePtr != 0)
	{
		// found it
		cout << "found " << nodePtr->data << endl;
	}
	else
	{
		cout << "not found " << parentPtr->data << endl;
	}

	intTree.deleteItem(4);
	intTree.insertNode(root, 14);

	cout << "\nInOrder Traversal after delete of 4 and insert of 14: ";
	intTree.inOrderTraversal(root);
	cout << endl;

	intRee.deleteItem(14);
	cout << "\nInOrder Traversal after delete of 14: ";
	intTree.inOrderTraversal(root);