//DELETION FROM A BINARY TREE

void testDelete (treePtr &root)

{

      int idToDelete;

      bool success;

      cout << "Testing delete algorithm" << endl << endl;

      cout << "Enter Id value to delete (-1 to quit) ---> ";

      cin >> idToDelete;

      while (idToDelete >= 0)

      {

            success = deleteNode (root, idToDelete);

            cout << "Id # " << idToDelete;

            if (!success)

                  cout << "     No such part in stock" << endl;

            else

                  cout << "     Id #" << idToDelete << " was deleted" << endl;

            cout << endl << "Enter Id value to delete (-1 to quit) ---> ";

            cin >> idToDelete;

      }

}

bool deleteNode (treePtr &p, int idToDelete)

// will recursively search for node with idToDelete, if found, calls modifyTree

{

      if (NULL == p)  return false;

      else if (idToDelete == p->id)

      {

            modifyTree (p);

            return true;

      }

      else if (idToDelete < p->id)

            return deleteNode(p->left, idToDelete);

      else

            return deleteNode (p->right, idToDelete);

}

void modifyTree (treePtr &p)

// p is either root or an internal pointer in the tree

// Algorithm deletes node pointed to by p.

{

      treePtr temp, marker = p;

      if ((NULL == p->right) && (NULL == p->left))      // leaf case

            p = NULL;

      else if (NULL == p->right)  // one-kid case, re-hook p to left child

            p = p->left;

      else if (NULL == p->left)     // other one-kid case, re-hook p to right child

            p = p->right;

      else     // 2-kid case

      {

            p = p->left;  // re-route pointer around node to be deleted

            temp = p;

            while (temp->right != NULL)

                  temp = temp->right;       // found new attachment point

            temp->right = marker->right;    // re-hook branch

      }

      delete marker;

}