/*--- File "BST" ---
 * Contains class template BST.
 *********************************************************/
#include <iostream>
using namespace std;

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

template <class DataType>
class BST
{
private:
/*** Node structure ***/
struct BinNode 
{
  DataType data;
  BinNode * left,
          * right;

  // BinNode constructor
  BinNode(DataType item)
  {
    data = item;
    left = right = 0;
  }
};

typedef BinNode * BinNodePointer; 

public:
/* Construct an empty BST.
 *   Precondition:  a BST has been declared
 *   Postcondition: an empty BST has been created
 *******************************************************/
BST();

/* Check if BST is empty.
 *   Receive: BST containing this function (implicitly)
 *   Return:  true if BST is empty, false otherwise
 *******************************************************/
bool Empty() const;

/* Search the BST for item.
 *
 * Receive: The BST containing this function (implicitly)
 *          item being searched for
 * Return:  true if item found, false otherwise
 ***********************************************************/
bool Search(const DataType & item) const; 

/* Insert item into BST.
 *
 * Receive:       The BST containing this function (implicitly)
 *                item being inserted
 * Postcondition: BST has been modified with item inserted
 *                at proper position to maintain BST property.
 *************************************************************/
void Insert(const DataType & item);

/* Inorder traversal.
 *
 * Receive: The BST containing this function (implicitly)
 *          ostream out
 * Output:  Contents of the BST in inorder
 *************************************************************/
void InOrder(ostream & out);

/* Inorder traversal auxiliary function
 *
 * Receive: The BST containing this function (implicitly)
 *          ostream out, and pointer ptr to a binary tree node
 * Output:  Contents of the BST with root at ptr in inorder
 *************************************************************/
void InOrderAux(ostream & out, BinNodePointer ptr);

/* Delete item from BST.
 *
 * Receive:       The BST containing this function (implicitly)
 *                item being deleted
 * Postcondition: BST has been modified with item removed (if
 *                present); BST property is maintained.
 * Note: Delete uses auxiliary function Search() to locate
 *       the node containing item and its parent.
 *************************************************************/

void Delete(const DataType & item);

/* Search2 locates node containing an item and its parent.
 *
 * Receive:   The BST containing this function (implicitly)
 *            item to be located
 * Pass back: Pointer locptr to node containing item -- null
 *              if not found -- and parent pointing to its
 *              parent
 *************************************************************/
void Search2(const DataType & item, bool & found,
             BinNodePointer & locptr, BinNodePointer & parent);

/*** Data members ***/
private:
  BinNodePointer root; 
}; // end of class template declaration

//--- Definition of constructor
template <class DataType>
inline BST<DataType>::BST()
{ root = 0; }

//--- Definition of Empty()
template <class DataType>
inline bool BST<DataType>::Empty() const
{ return root == 0; }

//--- Definition of Search()
template <class DataType>
bool BST<DataType>::Search(const DataType & item) const
{
  BinNodePointer locptr = root;
  bool found = false;
  for (;;)
  {
    if (found || locptr == 0) break;
    if (item < locptr->data)       // descend left
      locptr = locptr->left;
    else if (item > locptr->data)  // descend right
      locptr = locptr->right;
    else                           // item found
      found = true;
  }
  return found;
}

//--- Definition of Insert()
template <class DataType>
void BST<DataType>::Insert(const DataType & item)
{
  BinNodePointer 
     locptr = root,     // search pointer
     parent = 0;        // pointer to parent of current node
  bool found = false;   // indicates if item already in BST
  for (;;)
  {
    if (found || locptr == 0) break;
    parent = locptr;
    if (item < locptr->data)       // descend left
      locptr = locptr->left;
    else if (item > locptr->data)  // descend right
      locptr = locptr->right;
    else                           // item found
      found = true;
  }
  if (found)
    cout << "Item already in the tree\n";
  else
  {
    locptr = new BinNode(item);   // construct node containing item
    if (parent == 0)              // empty tree
      root = locptr;
    else if (item < parent->data) // insert to left of parent
      parent->left = locptr;
    else                          // insert to right of parent
      parent->right = locptr;
  }
}

//--- Definition of InOrder()
template <class DataType>
void BST<DataType>::InOrder(ostream & out)
{ InOrderAux(out, root); }

//--- Definition of InOrderAux()
template <class DataType>
void BST<DataType>::InOrderAux(ostream & out, BinNodePointer ptr)
{
  if (ptr != 0)
  {
    InOrderAux(out, ptr->left);
    out << ptr->data << "  ";
    InOrderAux(out, ptr->right);
  }
}

//--- Definition of Delete()
template <class DataType>
void BST<DataType>::Delete(const DataType & item)
{
  bool found;                      // signals if item is found
  BinNodePointer x,                // points to node containing
                 parent;           //    "    " parent of x and xSucc
  Search2(item, found, x, parent);

  if (!found)
  {
    cout << "Item not in the BST\n";
    return;
  }
  //else
  if (x->left != 0 && x->right != 0)
  {                                // node has 2 children
    // Find x's inorder successor and its parent
    BinNodePointer xSucc = x->right;
    parent = x;
    while (xSucc->left != 0)       // descend left
    {
      parent = xSucc;
      xSucc = xSucc->left;
    }

    // Move contents of xSucc to x and change x 
    // to point to successor, which will be deleted.
    x->data = xSucc->data;
    x = xSucc;
  } // end if node has 2 children

  // Now proceed with case where node has 0 or 2 child
  BinNodePointer subtree = x->left; // pointer to a subtree of x
  if (subtree == 0)
    subtree = x->right;
  if (parent == 0)                  // root being deleted
    root = subtree;
  else if (parent->left == x)       // left child of parent
    parent->left = subtree; 
  else                              // right child of parent
    parent->right = subtree;
  delete x;
}

//--- Definition of Search2()
template <class DataType>
void BST<DataType>::
Search2(const DataType & item, bool & found,
        BinNodePointer & locptr, BinNodePointer & parent)
{
  locptr = root;	
  parent = 0;
  found = false;
  for (;;)
  {
    if (found || locptr == 0) return;
    if (item < locptr->data)       // descend left
    {
      parent = locptr;
      locptr = locptr->left;
    }
    else if (item > locptr->data)  // descend right
    {
      parent = locptr;
      locptr = locptr->right;
    }
    else                           // item found
      found = true;
  }
}

#endif