// *****************************************************
// *                                                   *
// *   bstree.h (MP5)                                  *   
// *                                                   *
// *   Interface for a BST class                       * 
// *                                                   *
// *   Written by Mark Allen Weiss                     *
// *     Altered by Jason Zych                         * 
// *                                                   * 
// *****************************************************

#ifndef _BS_TREE 
#define _BS_TREE 

#include <iostream.h>
#include <stdlib.h>


// **************************************************************
// *                                                            *
// *  Class : TreeNode                                          *
// *                                                            *
// *  A node class for the BST implementation                   *
// *                                                            *
// **************************************************************

template <class Etype>
class TreeNode 
{
protected:
   
    // TreeNode
    //    - default constructor
    //    - initializes node to default values
    TreeNode() : element(), left(NULL), right(NULL) {}


    // TreeNode
    //    - constructor
    TreeNode( Etype E, TreeNode *L = NULL,
        TreeNode *R = NULL ) :
            element( E ), left( L ), right( R ) { }

    Etype element;
    TreeNode *left;
    TreeNode *right;

    friend class BSTree<Etype>;
};




// **************************************************************
// *                                                            *
// *  Class : Tree                                              *
// *                                                            *
// *  The interface class for the BST implementation            * 
// *                                                            *
// **************************************************************

template <class Etype>
class BSTree
{
public:

   // BSTree
   //    - default constructor
   //    - initializes tree to be empty
   BSTree();


   // BSTree
   //    - copy constructor
   //    - parameters : origVal - previously allocated BSTree object
   //    - initializes object to be a copy of origVal
   BSTree(const BSTree& origVal); 


   // ~BSTree
   //    - destructor
   //    - deletes dynamically allocated memory
   virtual ~BSTree(); 


   // operator=
   //    - parameters : origVal - previously allocated BSTree object
   //    - return value - const reference to this object  
   //    - sets object to be a copy of origVal
   const BSTree& operator=(const BSTree& origVal);


    
   void Make_Empty()
        { Make_Empty(root); root = lastFound = NULL; }


    void PreOrder() const
        { PreOrder(root); }

    void InOrder() const
        { InOrder(root); }

    void PostOrder() const
        { PostOrder(root); }

    virtual int Find(const Etype& X)
        { return int(lastFound = Find(X, root)); }

    virtual int Find_Min( )
        { return int(lastFound = Find_Min(root)); }

    virtual int Find_Max( )
        { return int(lastFound = Find_Max(root)); }

    virtual void Insert(const Etype& X)
        { Insert(X, root); }

    virtual void Remove(const Etype& X)
        { Remove(X, root); }


    virtual int IsEmpty() const
        { return (root == NULL); }

 
    // Last
    //    - returns element in the last node looked up 
    virtual Etype Last () const;


protected:

    void Make_Empty( TreeNode<Etype> * & T );
    void Insert( const Etype & X, TreeNode<Etype> * & T );
    void Remove( const Etype & X, TreeNode<Etype> * & T );
    void PreOrder( const TreeNode<Etype> * T ) const;
    void InOrder( const TreeNode<Etype> * T ) const;
    void PostOrder( const TreeNode<Etype> * T ) const;
  
    TreeNode<Etype> *
        Copy( const TreeNode<Etype> * T );
    TreeNode<Etype> *
        Find( const Etype & X, TreeNode<Etype> * T ) const;
    TreeNode<Etype> *
        Find_Min( TreeNode<Etype> * T ) const;
    TreeNode<Etype> *
        Find_Max( TreeNode<Etype> * T ) const;

    void BST_Error(const char *msg);

    TreeNode<Etype> *root;
    TreeNode<Etype> *lastFound;

};


#endif      
