TreeDelete(t,item):
|  Input  tree t, item
|  Output t with item deleted
|
|  if t is not empty then          // nothing to do for case 1
|  |  if item < data(t) then       // delete item in left subtree
|  |     left(t)=TreeDelete(left(t),item)
|  |  else if item > data(t) then  // delete item in right subtree
|  |     right(t)=TreeDelete(right(t),item)
|  |  else                         // node 't' must be deleted
|  |  |  if left(t) and right(t) are empty then 
|  |  |     new=empty tree                   // case 2: 0 children
|  |  |  else if left(t) is empty then
|  |  |     new=right(t)                     // case 3: 1 child
|  |  |  else if right(t) is empty then
|  |  |     new=left(t)                      // case 3: 1 child
|  |  |  else
|  |  |     new=joinTrees(left(t),right(t))  // case 4: 2 children
|  |  |  end if
|  |  |  free memory allocated for current node t
|  |  |  t=new
|  |  end if
|  end if
|  return t