with TEXT_IO ; use TEXT_IO ;
procedure TACCESS3 is  -- NOW, ADD AN  INSERT  PROCEDURE (data abstraction)
  type NODE ; -- just introduce type name
  type NODE_PTR is access NODE ; -- define an access type
                                 -- ie the type of a pointer
  type NODE is  -- now, really define the type NODE
    record
      BF    : INTEGER      ; -- balance factor for later use
      LEFT  : NODE_PTR     ; -- this records predecessor
      RIGHT : NODE_PTR     ; -- this records sucessor
      NAME  : STRING(1..2) ; -- data, the "sort" key
      PHONE : STRING(1..2) ; -- more tag along data
    end record ;
 
  ROOT_PTR   : NODE_PTR := null ;   -- initially null
 
  DEPTH : INTEGER := 1 ; -- indentation depth
 
  procedure OUTPUT(T : NODE_PTR ) is
    procedure INDENT is
    begin
      for I in 1..DEPTH loop
        PUT("    ") ;
      end loop ;
    end INDENT ;
  begin
    DEPTH := DEPTH + 1 ;  -- count depth "down" upon entry
    if T /= null then
      OUTPUT(T.LEFT) ;
      INDENT ; PUT(T.NAME) ; PUT_LINE(T.PHONE) ;
      OUTPUT(T.RIGHT) ;
    end if ;
    DEPTH := DEPTH - 1 ;  -- count depth "up" upon exit
  end OUTPUT ;
 
  procedure INSERT(T : in out NODE_PTR ; NAME,PHONE : STRING ) is
  begin
    if T = null then
      T := new NODE'(0, null, null, NAME, PHONE) ;
    else
      if NAME < T.NAME then
        INSERT(T.LEFT,NAME,PHONE) ;
      else
        INSERT(T.RIGHT,NAME,PHONE) ;
      end if ;
    end if ;
  end INSERT ;
 
 
begin
  PUT_LINE(" TREE INSERTION AND PRINTOUT") ;
  -- build a tree using the INSERT procedure
  INSERT(ROOT_PTR,"D ","4 ") ; -- initial node at root
    -- first tier
    INSERT(ROOT_PTR,"B ","2 ") ;
      -- replaces  LEFT_PTR := new NODE'(0, null, null, "B ", "2 ") ;
    INSERT(ROOT_PTR,"F ","6 ") ;
 
      -- second tier
      INSERT(ROOT_PTR,"A ","1 ") ;
      INSERT(ROOT_PTR,"C ","3 ") ;
      INSERT(ROOT_PTR,"E ","5 ") ;
      INSERT(ROOT_PTR,"G ","7 ") ;
 
  OUTPUT(ROOT_PTR) ; -- look at tree produced. The order of the tree
                     -- build was carefully planned to get a balanced
                     -- binary tree
 
end TACCESS3 ;


-- TREE INSERTION AND PRINTOUT 
--                A 1 
--            B 2 
--                C 3 
--        D 4 
--                E 5 
--            F 6 
--                G 7