Trees

In-Order Traversal (BST)

Recurse left, visit the node, recurse right. On a binary search tree the visit order is the values in ascending order — a key invariant that makes in-order traversal useful for BSTs specifically.

Algorithm

The canonical 7-node BST is built inline (root 4, left subtree with 1, 2, 3, right subtree with 5, 6, 7). In-order visit produces [1, 2, 3, 4, 5, 6, 7].

Basic Implementation

basic.f90 
module tree_mod
    implicit none
    type :: tree_node
        integer :: value
        type(tree_node), pointer :: left => null()
        type(tree_node), pointer :: right => null()
    end type tree_node

    integer :: output(7) = 0
    integer :: out_count = 0
contains
    recursive subroutine inorder(node)
        type(tree_node), pointer, intent(in) :: node
        if (.not. associated(node)) return
        call inorder(node%left)
        out_count = out_count + 1
        output(out_count) = node%value
        call inorder(node%right)
    end subroutine inorder
end module tree_mod

program tree_traversal
    use tree_mod
    implicit none
    type(tree_node), pointer :: n1, n2, n3, n5, n6, n7, root
    integer :: i

    allocate(n1); n1%value = 1
    allocate(n3); n3%value = 3
    allocate(n2); n2%value = 2; n2%left => n1; n2%right => n3
    allocate(n5); n5%value = 5
    allocate(n7); n7%value = 7
    allocate(n6); n6%value = 6; n6%left => n5; n6%right => n7
    allocate(root); root%value = 4; root%left => n2; root%right => n6

    call inorder(root)
    print '(*(I0,1X))', (output(i), i = 1, out_count)
end program tree_traversal

Complexity

  • Time: O(n)
  • Space: O(h) for the call stack

Implementation notes

  • Fortran: declare the recursive helper subroutine inorder(node) with recursive and a type(tree_node), pointer, intent(in) :: node dummy. The traversal collects values in a module-level output(:) array via a parallel out_count counter.
  • The replay emits one frame per visit(node) and shows the running output array, matching the lesson spec.
in-order recursion The visit happens between the two recursive calls.