///////////////////////////////////////////////////////
//
//	bst.cpp
//
///////////////////////////////////////////////////////

#include	<iostream>
#include	<stack>
#include	"bst.h"

BSTNode::BSTNode()
{
	mLeftChild = NULL;
	mRightChild = NULL;
	mParent = NULL;
	mData = 'A';
}


BSTNode::BSTNode( const BSTNode& node )
{
	mLeftChild = NULL;
	mRightChild = NULL;
	mParent = NULL;
	mData = node.mData;
}


BSTNode::BSTNode( char data )
{
	mLeftChild = NULL;
	mRightChild = NULL;
	mParent = NULL;
	mData = data;
}


BSTNode::~BSTNode()
{
	if( mLeftChild != NULL )
		delete mLeftChild;

	if( mRightChild != NULL )
		delete mRightChild;
}


BST::BST()
{
	mRoot = NULL;
}


BST::BST( const BST& b )
{
	// Not yet implemented
	mRoot = NULL;
}


BST::~BST()
{
	if( mRoot != NULL )
		delete mRoot;
}


void BST::AddItem( char data )
{
	if( mRoot == NULL )
	{
		mRoot = new BSTNode( data );
		if( mRoot == NULL )
			cerr << "Memory allocation error adding: " << data << endl;
		return;
	}


	BSTNode *pCurrentNode = mRoot;
	BSTNode *pParentOfCurrent = NULL;
	while( pCurrentNode != NULL )
	{
		if( data < pCurrentNode->mData )
		{
			pParentOfCurrent = pCurrentNode;
			pCurrentNode = pCurrentNode->mLeftChild;
		}

		else if( data == pCurrentNode->mData )
			return;

		else
		{
			pParentOfCurrent = pCurrentNode;
			pCurrentNode = pCurrentNode->mRightChild;
		}
	}

	pCurrentNode = new BSTNode( data );
	if( pCurrentNode == NULL )
	{
		cerr << "Memory trouble while adding: " << data << endl;
		return;
	}

	if( data < pParentOfCurrent->mData )
	{
		pParentOfCurrent->mLeftChild = pCurrentNode;
		pCurrentNode->mParent = pParentOfCurrent;
	}
	else
	{
		pParentOfCurrent->mRightChild = pCurrentNode;
		pCurrentNode->mParent = pParentOfCurrent;
	}
}


void BST::TraverseSubtree( BSTNode *root )
{
	if( root != NULL )
	{
		TraverseSubtree( root->mLeftChild );
		cout << root->mData << " ";
		TraverseSubtree( root->mRightChild );
	}
}


void BST::RTraverse()
{
	TraverseSubtree( mRoot );
	cout << endl;
}


void BST::ITraverse1()
{
	if( mRoot == NULL )
		return;

	stack<BSTNode *>	st;

	BSTNode *pCurrentNode = mRoot;
	while( pCurrentNode != NULL )
	{
		st.push( pCurrentNode );
		pCurrentNode = pCurrentNode->mLeftChild;
	}

	while( st.size() > 0 )
	{
		pCurrentNode = st.top();
		st.pop();

		cout << pCurrentNode->mData << " ";

		if( pCurrentNode->mRightChild != NULL )
		{
			pCurrentNode = pCurrentNode->mRightChild;
			while( pCurrentNode != NULL )
			{
				st.push( pCurrentNode );
				pCurrentNode = pCurrentNode->mLeftChild;
			}
		}
	}

	cout << endl;
}


void BST::ITraverse2()
{
	// Empty tree case.
	if( mRoot == NULL )
		return;

	// Get started at the far left node.
	BSTNode		*pCurrentNode = mRoot;
	while( pCurrentNode->mLeftChild != NULL )
		pCurrentNode = pCurrentNode->mLeftChild;


	// Do the traversal.
	while( pCurrentNode != NULL )
	{
		// Visit the node.
		cout << pCurrentNode->mData << " ";

		// Move to the next node.
		if( pCurrentNode->mRightChild != 0 )
		{
			pCurrentNode = pCurrentNode->mRightChild;
			while( pCurrentNode->mLeftChild != 0 )
				pCurrentNode = pCurrentNode->mLeftChild;
		}
		else
		{
			BSTNode *p = pCurrentNode->mParent;
			BSTNode *q = pCurrentNode;
			while( p != NULL  &&  p->mRightChild == q )
			{
				q = p;
				p = p->mParent;
			}
			pCurrentNode = p;
		}
	}

	cout << endl;
}