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

  IF T = NULL THEN
    T := MakeNode (E);
  ELSIF KeyOf(E) < KeyOf(T.Info) THEN
    IF T.Left = NULL THEN
      ConnectLeft (T, E);
    ELSE
      Insert (T.Left, E);
    END IF;
  ELSIF KeyOf(T.Info) < KeyOf(E) THEN
    IF T.Right = NULL THEN
      ConnectRight (T, E);
    ELSE
      Insert (T.Right, E);
    END IF;
  ELSE
    Insert(T.Right, E);
  END IF;

END Insert;