//******************************************
//
//   bst.C
//
// implementation of a minimal BST
// stolen from Mark Weiss text, then modified
//
// D. L. Frey  10/21/98
//
//  Note -- the class that's stored in the Tree_Nodes
// (Etype) must support the following operators
//   ==, <, >, <<, =
//********************************************

#include <assert.h>
#include "bst.h"

//*********************************************
// protected Find function, called by public Find
//
// recursive implementation
// finds node that matched T->Element
// returns pointer to node if found
// returns NULL if not found
//
//*******************************************
template <class Etype>
Tree_Node<Etype>*
Binary_Search_Tree<Etype>::Find( const Etype & X, Tree_Node<Etype> * T ) const
{
    if( T == NULL )
        return NULL;
    else
    if( X < T->Element )
        return Find( X, T->Left );
    else
    if( X > T->Element )
        return Find( X, T->Right );
    else
        return T;
}

//***************************************
// protected version of Insert, called by public Insert
//
// recursive version - returns void
//
// creates new node and sets T to point to it
// no affect if node is already in the tree
//
//**************************************
template <class Etype>
void 
Binary_Search_Tree<Etype>::Insert( const Etype & X, Tree_Node<Etype>* & T)
{
    if( T == NULL )
    {
        T = new Tree_Node<Etype>( X );
	assert (T);
	CurrentNode = T;
    }
    else if( X < T->Element )
    {
        Insert( X, T->Left );
    }
    else if( X > T->Element )
    {
        Insert( X, T->Right );
    }
    else
    {
	// node exists
	CurrentNode = T;
    }
}

//********************************
// protected MakeEmpty
//
// recursive routine to delete nodes
// starting "at the bottom" (leafs first)
//
// called only by BST destructor
//
//***********************************
template <class Etype>
void Binary_Search_Tree<Etype>::Make_Empty( Tree_Node<Etype> * & T )
{
    if( T != NULL )
    {
        Make_Empty( T->Left );
        Make_Empty( T->Right );
        delete T;
        T = NULL;
    }
}


//************************************
// protected Print_Tree, called by public version
//
// recursive in-order tree traversal
//
// relies on Etype's operator<< to output each node
//
//*************************************
template <class Etype>
void Binary_Search_Tree<Etype>::Print_Tree( Tree_Node<Etype> *T ) const
{
    if( T != NULL )
    {
        Print_Tree( T->Left );
        cout << T->Element << " " << endl;
        Print_Tree( T->Right );
    }
}

//*****************************
// protected Count_Nodes (T)
//
// recursively counts the number of nodes
//
//******************************

template <class Etype>
int Binary_Search_Tree<Etype>::Count_Nodes (Tree_Node<Etype> *T)
{
    if (T)
    {	
	return 1 + Count_Nodes (T->Left) + Count_Nodes (T->Right);
    }
    else
    {
	return 0;
    }
}