To complete our discussion of Binary Search Trees we need to discuss the deleteBST operation. The process would go something like the following:

Search for a node containing the "key" value

if (key not found)
  return
else if (either subtree is empty)
{
  delete the node replacing the parents link with the 
    ptr to the nonempty subtree or NULL if both 
    subtrees are empty
}
else
{
  Traverse the left subtree of the node to be deleted
    such that you find the rightmost node (Rnode) in the left
    subtree

  Move the content of Rnode to the node to be deleted

  Set Rnode's parent pointer to point to the left subtree
    of Rnode

  Free the storage from the unused node
}

P#1: Create a BST by inserting the months of the year in the following order: jan, mar, may, jul, sept, nov, feb, apr, jun, aug, oct, dec

P#2: Using the above algorithm, delete mar. Draw the resulting BST from deleting this node.

P#3: Using the above algorithm, delete jan. Draw the resulting BST from deleting this node.