PACKAGE BODY Binary_Search_Trees_Generic IS
------------------------------------------------------------------------
--| Body of Generic Binary Search Tree Package
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------

  -- local operations, not exported
  
  FUNCTION MakeNode (E : Element) RETURN Tree IS
  -- Pre:  E is defined
  -- Post: returns a pointer to a tree node containing E.
    Result : Tree;
  BEGIN
    Result := NEW BinaryTreeNode;
    Result.Info := E;
    RETURN Result;
  END MakeNode;

  PROCEDURE ConnectLeft (T : IN OUT Tree; E : Element) IS
  -- Pre:  T and E are defined; T.Left = NULL
  -- Post: creates a node containing E and connects it to
  --   the left subtree of T
  BEGIN
    T.Left := MakeNode (E);
  END ConnectLeft;

  PROCEDURE ConnectRight (T : IN OUT Tree; E : Element) IS
  -- Pre:  T and E are defined; T.Right = NULL
  -- Post: creates a node containing E and connects it to
  --   the right subtree of T
  BEGIN
    T.Right := MakeNode (E);
  END ConnectRight;

  PROCEDURE Initialize (T: IN OUT Tree) IS
  BEGIN
    T := NULL;
  END Initialize;
  
  FUNCTION Retrieve (T: Tree) RETURN Element IS
  BEGIN
    IF T = NULL THEN
      RAISE NotFound;
    ELSE
      RETURN T.Info;
    END IF;
  END Retrieve;
  
  FUNCTION Search (T: Tree; K : KeyType) RETURN Tree IS SEPARATE;

  PROCEDURE Insert (T : IN OUT Tree; E : Element) IS SEPARATE;

  FUNCTION FindSmallest (T : Tree) RETURN Tree IS SEPARATE;

  PROCEDURE Delete (T : IN OUT Tree; K : IN KeyType) IS SEPARATE;

  PROCEDURE Traverse_LNR (T : Tree) IS SEPARATE;

END Binary_Search_Trees_Generic;