! Program Example from "Essential Fortran 90 & 95" by Loren P. Meissner
! Copyright 1996. Copying for sale requires permission from the author.
! Otherwise, distribution is permitted if these three lines are included.

  module G33M

    implicit none
    public :: Look_Up, Print_Tree
    integer, parameter, private :: S_LEN = 20
    type, public :: Node_Type
      character (len = S_LEN) :: Key
      type (Node_Type), pointer :: Left_NP, Right_NP
    end type Node_Type
    character (len = S_LEN), public :: New_Key

  contains

    recursive subroutine Look_Up( Trav_NP )
      type (Node_Type), pointer :: Trav_NP
      type (Node_Type), pointer :: Temp_NP
  ! start subroutine Look_Up
      if (associated( Trav_NP )) then  ! Pointer is not NIL.
        if (New_Key == Trav_NP % Key) then
          write (unit = *, fmt = *) New_Key, " Found. "
        else if (New_Key > Trav_NP % Key) then
          call Look_Up (Trav_NP % Right_NP)  ! Recursion
        else  ! New_Key < Trav_NP % Key
          call Look_Up (Trav_NP % Left_NP)  ! Recursion
        end if
        return
      else  ! Insertion occurs only when Trav_NP is NIL.
        write (unit = *, fmt = *) New_Key, " Not found. "
        allocate( Temp_NP )
        Temp_NP % Key = New_Key
        nullify( Temp_NP % Left_NP )
        nullify( Temp_NP % Right_NP )
        Trav_NP => Temp_NP  ! Assign to argument pointer.
      end if
      return
    end subroutine Look_Up

    recursive subroutine Print_Tree( Arg_NP )
      type (Node_Type), pointer :: Arg_NP
  ! start subroutine Print_Tree
      if (associated( Arg_NP )) then
        call Print_Tree( Arg_NP % Left_NP )
        write (unit = *, fmt = *) Arg_NP % Key
        call Print_Tree( Arg_NP % Right_NP )
      end if
      return
    end subroutine Print_Tree

  end module G33M
