Segmentation faults in Fortran recursive tree implementation

Question

I need to implement a tree structure in Fortran for a project, so I've read various guides online explaining how to do it. However, I keep getting errors or weird results.

Let's say I want to build a binary tree where each node stores an integer value. I also want to be able to insert new values into a tree and to print the nodes of the tree. So I wrote a type "tree" that contains an integer, two pointers towards the children sub-trees and a boolean which I set to .true. if there are no children sub-trees:

module class_tree
implicit none

type tree
    logical :: isleaf
    integer :: value
    type (tree), pointer :: left,right
end type tree

interface new
    module procedure newleaf
end interface

interface insert
    module procedure inserttree
end interface

interface print
    module procedure printtree
end interface

contains

subroutine newleaf(t,n)
    implicit none
    type (tree), intent (OUT) :: t
    integer, intent (IN) :: n

    t % isleaf = .true.
    t % value = n
    nullify (t % left)
    nullify (t % right)
end subroutine newleaf

recursive subroutine inserttree(t,n)
    implicit none
    type (tree), intent (INOUT) :: t
    integer, intent (IN) :: n
    type (tree), target :: tleft,tright

    if (t % isleaf) then
        call newleaf(tleft,n)
        call newleaf(tright,n)

        t % isleaf = .false.
        t % left => tleft
        t % right => tright
    else
        call inserttree(t % left,n)
    endif
end subroutine inserttree

recursive subroutine printtree(t)
    implicit none
    type (tree), intent (IN) :: t

    if (t % isleaf) then
        write(*,*) t % value
    else
        write(*,*) t % value
        call printtree(t % left)
        call printtree(t % right)
    endif
end subroutine printtree
end module class_tree

The insertion is always done into the left sub-tree unless trying to insert into a leaf. In that case, the insertion is done into both sub-trees to make sure a node has always 0 or 2 children. The printing is done in prefix traversal.

Now if I try to run the following program:

program main
use class_tree
implicit none
type (tree) :: t

call new(t,0)
call insert(t,1)
call insert(t,2)
call print(t)
end program main

I get the desired output 0 1 2 2 1. But if I add "call insert(t,3)" after "call insert(t,2)" and run again, the output is 0 1 2 0 and then I get a segfault.

I tried to see whether the fault happened during insertion or printing so I tried to run:

program main
use class_tree
implicit none
type (tree) :: t

call new(t,0)
call insert(t,1)
call insert(t,2)
write(*,*) 'A'
call insert(t,3)
write(*,*) 'B'
call print(t)
end program main

It makes the segfault go away but I get a very weird output A B 0 1 2673568 6 1566250180.

When searching online for similar errors, I got results like here where it says it might be due to too many recursive calls. However, the call to insert(t,3) should only contain 3 recursive calls... I've also tried to compile using gfortran with -g -Wall -pedantic -fbounds-check and run with a debugger. It seems the fault happens at the "if (t % isleaf)" line in the printing subroutine, but I have no idea how to make sense of that.

Edit:

Following the comments, I have compiled with -g -fbacktrace -fcheck=all -Wall in gfortran and tried to check the state of the memory. I'm quite new to this so I'm not sure I'm using my debugger (gdb) correctly.

After the three insertions and before the call to print, it seems that everything went well: for example when I type p t % left % left % right % value in gdb I get the expected output (that is 3). If I just type p t, the output is (.FALSE.,0,x,y), where x and y are hexadecimal numbers (memory addresses, I guess). However, if I try p t % left, I get something like a "description" of the pointer:

PTR TO -> (Type tree
logical(kind=4) :: isleaf
integer(kind=4) :: value

which repeats itself a lot since each pointer points to a tree that contains two pointers. I would have expected an output similar to that of p t, but I have no idea whether that's normal.

I also tried to examine the memory: for example if I type x/4uw t % left, I get 4 words, the first 2 words seem to correspond to isleaf and value, the last 2 to memory addresses. By following the memory addresses like that, I managed to visit all the nodes and I didn't find anything wrong.

The segfault happens within the printing routine. If I type p t after the fault, it says I cannot access the 0x0 address. Does that mean my tree is somehow modified when I try to print it?

Answer 1

The reason for your problems is the fact, that variables, which get out of scope, are not valid anymore. This is in contrast to languages like Python, where the number of existing pointers is relevant (refcount).

In your particular case, this means, that the calls to newleaf(left, n) and newleaf(right, n) set the values of left and right, resp., but these variables get ouf of scope and, thus, invalid.

A better approach is to allocate each leaf as it is needed (except the first one, since this is already allocated and will not get out of scope till the end of the program).

recursive subroutine inserttree(t,n)
  implicit none
  type (tree), intent (INOUT) :: t
  integer, intent (IN) :: n

  if (t % isleaf) then
    allocate(t%left)
    allocate(t%right)
    call newleaf(t%left,n)
    call newleaf(t%right,n)

    t % isleaf = .false.
  else
    call inserttree(t % left,n)
  endif
end subroutine inserttree