/*--- BST.h ----------------------------------------------------------------
  Your Name 
  yname@online.tamu-commerce.edu
  Assignment #5 - Binary Search Trees
  June 28, 2005
  Compiler used

This header file contains the class template BST.
  Basic operations:
     Constructor: Constructs an empty BST
	 Destructor:  Frees up memory used by BST
     empty:       Checks if a BST is empty
     search:      Search a BST for an item
     insert:      Inserts a value into a BST
     remove:      Removes a value from a BST
     graph:       Output a grapical representation of a BST
  Private utility helper operations:
     search2:     Used by delete
     inorderAux:  Used by inorder
     graphAux:    Used by graph
  Operations tp be added:
     inorder, preorder and  postorder traversals

---------------------------------------------------------------------------*/

#include <iostream>
//#include <new>
using namespace std;

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

typedef int DataType;

class BST
{
 public:
  /***** Function Members *****/
  /*------------------------------------------------------------------------
    Construct a BST object.

    Precondition:  None.
    Postcondition: An empty BST has been constructed.
   -----------------------------------------------------------------------*/
  BST();

  /*------------------------------------------------------------------------
    Destruct a BST object.

    Precondition:  None.
    Postcondition: All allocated memory of the BST has been freed.
   -----------------------------------------------------------------------*/
  ~BST();

  /*------------------------------------------------------------------------
    Check if BST is empty.

    Precondition:  None.
    Postcondition: Returns true if BST is empty and false otherwise.
   -----------------------------------------------------------------------*/
  bool empty() const;

  /*------------------------------------------------------------------------
    Search the BST for item.

    Precondition:  None.
    Postcondition: Returns true if item found, and false otherwise.
   -----------------------------------------------------------------------*/
  bool search(const DataType & item) const; 
   
  /*------------------------------------------------------------------------
    Insert item into BST.

    Precondition:  None.
    Postcondition: BST has been modified with item inserted at proper 
        position to maintain BST property. 
  ------------------------------------------------------------------------*/
  void insert(const DataType & item);
  
  /*------------------------------------------------------------------------
    Remove item from BST.

    Precondition:  None.
    Postcondition: BST has been modified with item removed (if present);
        BST property is maintained.
    Note: remove uses private auxiliary function search2() to locate 
          the node containing item and its parent.
 ------------------------------------------------------------------------*/
  void remove(const DataType & item);

  /*------------------------------------------------------------------------
    Graphic output of BST.

    Precondition:  ostream out is open.
    Postcondition: Graphical representation of BST has been output to out.
    Note: graph() uses private auxiliary function graphAux().
 ------------------------------------------------------------------------*/
  void graph(ostream & out) const;
 


  //--- ADD PROTOTYPES OF inorder() preorder() AND postorder() HERE

 
 private:
  /***** Node class *****/
  class BinNode 
  {
   public:
    DataType data;
    BinNode * left;
    BinNode * right;

    // BinNode constructors
    // Default -- data part is default DataType value; both links are null.
    BinNode()
    : left(0), right(0)
    {}

    // Explicit Value -- data part contains item; both links are null.
    BinNode(DataType item)
    : data(item), left(0), right(0)
    {}
 
  };// end of class BinNode declaration

  typedef BinNode * BinNodePointer; 
  
  /***** Private Function Members *****/
  
  /*------------------------------------------------------------------------
    Locate a node containing item and its parent.
 
    Precondition:  None.
    Postcondition: locptr points to node containing item or is null if 
        not found, and parent points to its parent.#include <iostream>
  ------------------------------------------------------------------------*/
  void search2(const DataType & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent) const;
 
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Subtree with root pointed to by subtreePtr has been
        output to out.
  ------------------------------------------------------------------------*/
  void inorderAux(ostream & out, 
                  BinNodePointer subtreePtr) const;
 
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree with root pointed 
        to by subtreePtr has been output to out, indented indent spaces.
  ------------------------------------------------------------------------*/
  void graphAux(ostream & out, int indent,
                      BinNodePointer subtreeRoot) const;
 
 /***** Data Members *****/
  BinNodePointer myRoot; 

}; // end of class template declaration


#endif