///////////////////////////////////////////////////////////////
// Corrected version of the textbook's BST::Delete(T &) method
//
// T. Anastasio
// Created: 16 March 1999
// Current: 17 March 1999
///////////////////////////////////////////////////////////////


template<class T>
bool BST<T>::Delete(T & item)
{
  bool found;
  Bnode<T>* v = Search(root, item, found);
  if (found == false)
    return false;

  Bnode<T>* pv = NULL;

  if (v == root) // make fake parent for the root node
    {            // so v->parent will not be null
      pv = new Bnode<T>;
      v->parent = pv;
      pv->lchild = v;  // arbitrarily make v a lchild
    }

  if (v->lchild == 0 || v->rchild == 0)   // case 1 or 2
    {
      if (v->lchild != 0)   // case 2, v has a left child
	{
	  if (v->parent->lchild == v)   
	    {  // v is a left child
	      v->parent->lchild = v->lchild;
	      v->lchild->parent = v->parent;
	    }
	  else    
	    {  // v is a right child
	      v->parent->rchild = v->lchild;
	      v->lchild->parent = v->parent;
	    }

	  if (v == root)
	    root = v->lchild;
	}  ///////////////////////
      else if (v->rchild != 0)   // case 2, v has a right child
	{
	  if (v->parent->lchild == v)    
	    { // v is a left child
	      v->parent->lchild = v->rchild;
	      v->rchild->parent = v->parent;
	    }
	  else  
	    { // v is a right child
	      v->parent->rchild = v->rchild;
	      v->rchild->parent = v->parent;
	    }
	  
	  if (v == root)
	    root = v->rchild;
	}
      else  // case 1  (v is a leaf)
	{
	  if (v->parent->lchild == v)
	    v->parent->lchild = 0;
	  else
	    v->parent->rchild = 0;

	  if (v == root)
	    root = 0;
	}
      delete v;
    }
  else   // case 3
    {
      Bnode<T>* p = SubtreeMax(v->lchild);  // p is the predecessor of v
      v->data = p->data;
      if (p->lchild != 0)   // case 2, p has a left child
	{
	  if (p->parent->lchild == p)
	    p->parent->lchild = p->lchild;
	  else
	    p->parent->rchild = p->lchild;
	  p->lchild->parent = p->parent;
	}
      else if (p->rchild != 0)   // case 2, p has a right child
	{
	  if (p->parent->lchild == p)
	    p->parent->lchild = p->rchild;
	  else
	    p->parent->rchild = p->rchild;
	  p->rchild->parent = p->parent;
	}
      else  // case 1
	if (p->parent->lchild == p)
	  p->parent->lchild = 0;
	else
	  p->parent->rchild = 0;
      delete p;
    }
  delete pv;
  return true;
}