/* File BST contains the declarations and definitions of
 * BST, a class template for binary search trees.
 *
 * Written by:   Larry R. Nyhoff
 * Written for:  Lab Manual for C++: An Introduction to Data Structures
 *
 * Add descriptions of the basic operations and other documentation required 
 * by your instructor such as your name, course number, and the current date.
 *************************************************************************/

#include <iostream>
using namespace std;

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

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

    // BinNode constructors
    // Default -- data part undefined; both links null
    BinNode()
    { left = right = 0; }

    // Explicit Value -- data part contains item; both links null
    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 (via InorderAux)
 *************************************************************/
 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 Search2() 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 <typename DataType>
inline BST<DataType>::BST()
{ root = 0; }


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


//--- Definition of Search()
template <typename 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 <typename 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)
    cerr << "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 <typename DataType>
void BST<DataType>::Inorder(ostream & out)
{ InorderAux(out, root); }


//--- Definition of InorderAux()
template <typename 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 <typename DataType>
void BST<DataType>::Delete(const DataType & item)
{
  bool found;          // signals if item is found
  BinNodePointer x,    // points to node containing item
  parent;              // R R parent of x and xSucc

  Search2(item, found, x, parent);
  if (!found)
  {
    cerr << "Item not in the BST\n";
    return;
  }

  //else
  if (x->left != 0 && x->right != 0)
  { // node has 2 children
    // Find xUs 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 1 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 <typename 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