SEPARATE (Binary_Search_Trees_Generic)
PROCEDURE Delete (T : IN OUT Tree; K : IN KeyType) IS
------------------------------------------------------------------------
--| BST Delete Operation, subunit of Binary_Search_Trees_Generic
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------
  Temp: Tree;
BEGIN -- Delete

  IF T = NULL THEN
    RAISE NotFound;
  END IF;
  
  IF K < KeyOf(T.Info) THEN              -- check left subtree
    Delete (T.Left, K);
  ELSIF KeyOf(T.Info) < K THEN           -- check right subtree
    Delete (T.Right, K);          
  ELSE                            -- delete this node
    IF T.Left = NULL AND T.Right = NULL THEN
      T := NULL;                  -- T is a leaf; delete it
    ELSIF T.Right = NULL THEN     -- replace T by its predecessor
      T := T.Left;
    ELSIF T.Left = NULL THEN      -- replace T by its successor
      T := T.Right;
    ELSE                          -- both children there
      Temp := FindSmallest(T.Right);
      T.Info := Temp.Info;
      Delete(T.Right, KeyOf(T.Info));    
    END IF;
  END IF;

END Delete;