SEPARATE (BST_Threaded_Generic)
PROCEDURE Insert (T : IN OUT Tree; E : ElementType) IS 
------------------------------------------------------------------------
--| Nonrecursive Insert procedure for Threaded BST
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------

  Current: Tree;
  Temp   : Tree;

  FUNCTION MakeNode(E: ElementType) RETURN Tree IS
    Result: Tree;
  BEGIN
    Result := NEW BinaryTreeNode;
    Result.Info := E;
    RETURN Result;
  END MakeNode;

BEGIN -- Insert

  IF T = NULL THEN
    T := MakeNode (E);
    RETURN;
  END IF;

  Current := T;
  LOOP
    IF E < Current.Info THEN
      IF Current.Left = NULL THEN   -- Connect to left subtree
        Current.Left := MakeNode (E);
        Current.Left.Thread := True;
        Current.Left.Right := Current;
        EXIT;
      ELSE
        Current := Current.Left;
      END IF;

    ELSE                            -- Equal treated as greater
      IF Current.Right = NULL OR Current.Thread THEN
        Current.Thread := False;
        Temp := MakeNode (E);       -- Connect to right subtree
        IF Current.Right /= NULL THEN
          Temp.Thread := True;
          Temp.Right := Current.Right;
        END IF;
        Current.Right := Temp;
        EXIT;
      ELSE
        Current := Current.Right;
      END IF;
    END IF;
      
  END LOOP;

END Insert;