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

  This implementation 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 <iomanip>
#include <iostream>
using namespace std;
#include "BST.h"



//--- Definition of constructor
BST::BST() : myRoot(0)
{}



//--- Definition of destructor
BST::~BST()
{
	// left blank
}



//--- Definition of empty()
bool BST::empty() const
{ 
	return myRoot == 0; 
}



//--- Definition of search()
bool BST::search(const DataType & item) const
{
   BST::BinNodePointer locptr = myRoot;
   bool found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
        locptr = locptr->left;
      else if (locptr->data < item)  // descend right
        locptr = locptr->right;
      else                           // item found
        found = true;
   }
   return found;
}



//--- Definition of insert()
void BST::insert(const DataType & item)
{
   BST::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item
      locptr = new(nothrow) BST::BinNode(item);  
      if (locptr == 0)	
      {
        cerr << "*** Out of memory -- terminating program ***\n";
	exit(1);
      }

      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   else
      cout << "Item already in the tree\n";
}



//--- Definition of remove()
void BST::remove(const DataType & item)
{
   bool found;                      // signals if item is found
   BST::BinNodePointer 
      x,                            // points to node to be deleted
      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
      BST::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 removed.
     x->data = xSucc->data;
     x = xSucc;
   } // end if node has 2 children

   // Now proceed with case where node has 0 or 2 child
   BST::BinNodePointer 
      subtree = x->left;             // pointer to a subtree of x
   if (subtree == 0)
      subtree = x->right;
   if (parent == 0)                  // root being removed
      myRoot = 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 graph()
void BST::graph(ostream & out) const
{
	graphAux(out, 0, myRoot);
}



//--- Definition of search2()
void BST::search2(const DataType & item, bool & found,
                            BinNodePointer & locptr, 
                            BinNodePointer & parent) const
{
   locptr = myRoot;
   parent = 0;
   found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
      {
         parent = locptr;
         locptr = locptr->left;
      }
      else if (locptr->data < item)  // descend right
      {
         parent = locptr;
         locptr = locptr->right;
      }
      else                           // item found
         found = true;
   }
}



//--- Definition of graphAux()
void BST::graphAux(ostream & out, int indent, 
                             BinNodePointer subtreeRoot) const
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}




//--- PUT DEFINITIONS OF THE ADDED OPERATIONS HERE