DELETING A NODE FROM A TREE:

Deleting a node with 0 children:  just remove it from the tree.  This does mean adjusting pointers in the parent node.  (If you are deleting the root, this will require a change in the root pointer.)

Deleting a node with 1 child:  Move the pointers around the node so that your parent and your child are now directly connected to each other.  (If you are deleting the root, this will require a change in the root pointer.)

Deleting a node with 2 children:

  Find the "next" node.  (Move right once, left all the way down.)
  Copy the key and data information from the next node into the node you want to delete.
  The next node is guaranteed to have only 0 or 1 child.  Delete the next node using the appropriate rule.