// TREE.H
// Definition of template class Tree
#ifndef TREE_H
#define TREE_H

#include <iostream.h>
#include <assert.h>
#include "treenode.h"
#include "slistnd.h"
#include "slist.h"
/****************************************************************************
*
*
*
****************************************************************************/
template< class NODETYPE >
class Tree{
public:
   Tree();
   void insertNode( const NODETYPE &, const NODETYPE & );
   void inOrderTraversal() const;
   void searchTree( const  NODETYPE &);
protected:
	void searchTreehelper( TreeNode< NODETYPE>*, const NODETYPE &);
   TreeNode<NODETYPE> *rootPtr;

   // utility functions
   void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & ,
												const NODETYPE &);
   void inOrderHelper( TreeNode< NODETYPE > * ) const; //?what is passed?
   
};
/****************************************************************************
*
*
*
****************************************************************************/
template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; }

template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value,
											const NODETYPE & data2 )
   { insertNodeHelper( &rootPtr, value, data2 ); }

// This function receives a pointer to a pointer so the
// pointer can be modified.
// NOTE: THIS FUNCTION WAS MODIFIED TO ALLOW DUPLICATES.
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr,
                      const NODETYPE &value, const NODETYPE &data2)
{
	if ( *ptr == 0 )
	{                   // tree is empty
      *ptr = new TreeNode< NODETYPE >( value );
      assert( *ptr != 0 );
	  
	  (*ptr)->S._insertAtFront(data2);
	 }
	else                              // tree is not empty
	{  
	     if  ( value < ( *ptr ) -> data )
            insertNodeHelper( &( ( *ptr ) -> leftPtr ), value, data2 );
		 else
		 {
			if ( value > (*ptr )->data)
				insertNodeHelper( &( ( *ptr ) -> rightPtr ), value, data2 );
			else
			{
				(*ptr)->S._insertAtFront(data2);
			}
		 }
	}  

}
//Inorder 
template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const 
{ inOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
   if ( ptr != 0 )
   {
      inOrderHelper( ptr -> leftPtr );
	
      cout << ptr -> data << ' ';

      inOrderHelper( ptr -> rightPtr );
   }
   
}

template< class NODETYPE >
void Tree< NODETYPE >::searchTree(const NODETYPE &temp) 
{	
	searchTreehelper(rootPtr, temp);}
template< class NODETYPE >
void Tree< NODETYPE >::searchTreehelper( TreeNode < NODETYPE > *root,
											const NODETYPE &temp)
{	
	if(!root)
		cout <<"The List Is Empty!!\n\n";
		
	while (root->data!=temp)
	{
		if(temp<root->data)
			root = root->leftPtr;
		else
			root = root->rightPtr;

			if(root==NULL)break;
	}
	root->S._print();
}
#endif
/****************************************************************************
*
*
*
****************************************************************************/