Fortran binary trees
last modified November 14, 2026
A linked list follows one pointer per value, so it can answer "what comes next" but not "where is 42". A binary tree gives every node two pointers, a left one and a right one, and orders the values so that the left subtree holds smaller values and the right subtree larger ones. A tree that follows this rule is a binary search tree: from the root the search turns left or right at every node, and in a balanced tree each turn halves the number of candidates. The same structure answers questions about order, such as the smallest value, the largest, or all values between two limits, without sorting anything again.
This article builds a binary search tree from a self-referential type, inserts and searches values, walks the nodes in the three classic orders, measures the tree, deletes nodes in all three cases, and finally releases the whole structure. Every routine is recursive, because a tree is defined in terms of smaller trees.
A node with two pointers
The type node holds a value and two pointers to further nodes,
each defaulting to null. A null pointer is the mark of an empty subtree, so a
tree of any size is described by the one pointer to its root, and that single
pointer stands for the whole tree. The insert routine is
recursive: at an empty position it allocates the new node, otherwise it
compares the value with the current one and descends into the left or the right
pointer. Because the dummy argument is a pointer with intent(inout),
the assignment to it changes the caller's pointer, which is how the new node
gets attached.
module bst
implicit none
private
public :: node, insert, inorder
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
recursive subroutine inorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
call inorder(root%left)
write (*, '(i0, 1x)', advance='no') root%value
call inorder(root%right)
end subroutine inorder
end module bst
program b1
use bst
implicit none
type(node), pointer :: root => null()
integer :: values(7), i
values = [50, 30, 70, 20, 40, 60, 80]
do i = 1, size(values)
call insert(root, values(i))
end do
print *, 'in order:'
call inorder(root)
print *
print *, 'root: ', root%value
print *, 'left child: ', root%left%value
print *, 'right child: ', root%right%value
end program b1
Inserting 50, 30, 70, 20, 40, 60 and 80 builds a tree with 50 at the root, 30 and 70 below it, and four leaves. The in-order walk prints the values in ascending order, which is not a coincidence: it visits the left subtree first, then the node, then the right subtree, and the search tree rule guarantees that everything on the left is smaller. Values equal to an existing node are ignored by the two comparisons, so the tree holds each value once unless the rules are changed.
$ gfortran b1.f90 -o b1 $ ./b1 in order: 20 30 40 50 60 70 80 root: 50 left child: 30 right child: 70
Traversal orders
A traversal visits every node once and does something with it. The three orders differ only in where the node itself is handled: pre-order handles the node before its subtrees, in-order between them, and post-order after both. All three are written with the same two recursive calls and one statement, and all three run in time proportional to the number of nodes. Pre-order reproduces the shape of the tree from the root down, in-order produces sorted output, and post-order is what a program uses when it must handle the children before the parent.
module walks
implicit none
private
public :: node, insert, preorder, inorder, postorder
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
recursive subroutine preorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
write (*, '(i0, 1x)', advance='no') root%value
call preorder(root%left)
call preorder(root%right)
end subroutine preorder
recursive subroutine inorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
call inorder(root%left)
write (*, '(i0, 1x)', advance='no') root%value
call inorder(root%right)
end subroutine inorder
recursive subroutine postorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
call postorder(root%left)
call postorder(root%right)
write (*, '(i0, 1x)', advance='no') root%value
end subroutine postorder
end module walks
program b2
use walks
implicit none
type(node), pointer :: root => null()
integer :: values(9), i
values = [50, 30, 70, 20, 40, 60, 80, 35, 65]
do i = 1, size(values)
call insert(root, values(i))
end do
write (*, '(a)', advance='no') 'preorder: '
call preorder(root)
print *
write (*, '(a)', advance='no') 'inorder: '
call inorder(root)
print *
write (*, '(a)', advance='no') 'postorder: '
call postorder(root)
print *
end program b2
The same nine values produce three different sequences. Pre-order starts at 50 and always takes the left branch first, in-order sorts, and post-order ends with the root, which is the property that makes it useful for freeing memory. The extra nodes 35 and 65 hang below 40 and 60, and they appear in their sorted places in the in-order line, which shows that the shape follows the insertion order while the in-order sequence does not.
$ gfortran b2.f90 -o b2 $ ./b2 preorder: 50 30 20 40 35 70 60 65 80 inorder: 20 30 35 40 50 60 65 70 80 postorder: 20 35 40 30 65 60 80 70 50
Searching a tree
Searching needs no recursion at all. A loop keeps a pointer to the current node, compares the sought value with the node's value, and moves to the left or the right child. The loop ends when the value matches or when the pointer becomes null, which means the value is absent. In a balanced tree the number of visited nodes is close to the base-two logarithm of the size, so a thousand values need about ten comparisons instead of a thousand.
module search_mod
implicit none
private
public :: node, insert, contains, steps
integer :: steps = 0
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
logical function contains(root, value) result(found)
type(node), pointer, intent(in) :: root
integer, intent(in) :: value
type(node), pointer :: cur
steps = 0
cur => root
found = .false.
do while (associated(cur))
steps = steps + 1
if (value == cur%value) then
found = .true.
return
else if (value < cur%value) then
cur => cur%left
else
cur => cur%right
end if
end do
end function contains
end module search_mod
program b3
use search_mod
implicit none
type(node), pointer :: root => null()
integer :: values(9), i, probes(4)
values = [50, 30, 70, 20, 40, 60, 80, 35, 65]
do i = 1, size(values)
call insert(root, values(i))
end do
probes = [35, 50, 65, 55]
do i = 1, size(probes)
print '(a, i0, a, l1, a, i0)', 'look for ', probes(i), ': ', &
contains(root, probes(i)), ', nodes visited ', steps
end do
end program b3
The value 50 is found in one probe because it sits at the root, while 35 and 65
need four probes, one for each level they occupy. The missing value 55 takes
three probes and ends at a null pointer below 60, which is the same path a
search for a value that belongs there would take. The module variable
steps counts the probes so that the program can report them;
a production search would return the count or take it as an argument.
$ gfortran b3.f90 -o b3 $ ./b3 look for 35: T, nodes visited 4 look for 50: T, nodes visited 1 look for 65: T, nodes visited 4 look for 55: F, nodes visited 3
Size, height and leaves
Three measurements follow the same recursive shape. The size is one plus the sizes of both subtrees, the height is one plus the larger of the two subtree heights, and the number of leaves counts the nodes that have no children at all. All three return zero for an empty subtree, which makes the recursion terminate without a separate test at every call. These functions take the root by pointer and never modify it.
module stats
implicit none
private
public :: node, insert, size_of, height_of, leaves_of
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
recursive integer function size_of(root) result(n)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) then
n = 0
else
n = 1 + size_of(root%left) + size_of(root%right)
end if
end function size_of
recursive integer function height_of(root) result(h)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) then
h = 0
else
h = 1 + max(height_of(root%left), height_of(root%right))
end if
end function height_of
recursive integer function leaves_of(root) result(n)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) then
n = 0
else if (.not. associated(root%left) .and. &
.not. associated(root%right)) then
n = 1
else
n = leaves_of(root%left) + leaves_of(root%right)
end if
end function leaves_of
end module stats
program b4
use stats
implicit none
type(node), pointer :: root => null(), chain => null()
integer :: values(9), i
values = [50, 30, 70, 20, 40, 60, 80, 35, 65]
do i = 1, size(values)
call insert(root, values(i))
end do
print '(a, i0)', 'nodes: ', size_of(root)
print '(a, i0)', 'height: ', height_of(root)
print '(a, i0)', 'leaves: ', leaves_of(root)
do i = 1, 5
call insert(chain, i * 10)
end do
print '(a, i0, a, i0)', 'sorted input, ', size_of(chain), &
' nodes, height ', height_of(chain)
end program b4
The nine values form a tree of height four with four leaves. The second tree is built from values that arrive in ascending order, and it degenerates into a chain: five nodes and height five. The height is what decides the cost of a search, so the same insertion routine can produce a fast tree or a slow one depending on the order of the input. A balanced tree keeps the height near the logarithm by rearranging nodes on insertion, a refinement that costs extra code and is the reason balanced trees exist at all.
$ gfortran b4.f90 -o b4 $ ./b4 nodes: 9 height: 4 leaves: 4 sorted input, 5 nodes, height 5
Minimum, maximum and ranges
The smallest value of a search tree is the leftmost node, because every step to the left goes to a smaller value; the largest is the rightmost node. Both are found with a short loop and neither needs to visit the whole tree. A range query is slightly more interesting: it walks the tree recursively but skips subtrees that cannot contain a value in the requested interval, and prints the values it meets in ascending order.
module ranges
implicit none
private
public :: node, insert, minimum, maximum, in_range
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
integer function minimum(root) result(v)
type(node), pointer, intent(in) :: root
type(node), pointer :: cur
cur => root
do while (associated(cur%left))
cur => cur%left
end do
v = cur%value
end function minimum
integer function maximum(root) result(v)
type(node), pointer, intent(in) :: root
type(node), pointer :: cur
cur => root
do while (associated(cur%right))
cur => cur%right
end do
v = cur%value
end function maximum
recursive subroutine in_range(root, low, high)
type(node), pointer, intent(in) :: root
integer, intent(in) :: low, high
if (.not. associated(root)) return
if (root%value > low) call in_range(root%left, low, high)
if (root%value >= low .and. root%value <= high) &
write (*, '(i0, 1x)', advance='no') root%value
if (root%value < high) call in_range(root%right, low, high)
end subroutine in_range
end module ranges
program b5
use ranges
implicit none
type(node), pointer :: root => null()
integer :: values(9), i
values = [50, 30, 70, 20, 40, 60, 80, 35, 65]
do i = 1, size(values)
call insert(root, values(i))
end do
print '(a, i0)', 'minimum: ', minimum(root)
print '(a, i0)', 'maximum: ', maximum(root)
write (*, '(a)', advance='no') 'between 35 and 65: '
call in_range(root, 35, 65)
print *
write (*, '(a)', advance='no') 'between 41 and 59: '
call in_range(root, 41, 59)
print *
end program b5
The minimum is 20 and the maximum 80, as expected from the leftmost and
rightmost paths. The range from 35 to 65 yields five values in order, and the
narrow range from 41 to 59 yields only 50. The pruning tests
root%value > low and root%value < high decide
whether the left or the right subtree can still hold a candidate; without them
the routine would visit every node and produce the same answer more slowly.
$ gfortran b5.f90 -o b5 $ ./b5 minimum: 20 maximum: 80 between 35 and 65: 35 40 50 60 65 between 41 and 59: 50
Deleting a node
Deletion is the operation that separates a real tree from a demonstration, because the node to remove may have zero, one or two children. A node without children is simply deallocated. A node with one child is replaced by that child, so the child is linked in its place. A node with two children cannot be replaced by both, so its value is overwritten with the smallest value of its right subtree and that smallest node is then deleted instead; it has no left child, so the first two cases remove it.
module deletable
implicit none
private
public :: node, insert, delete_node, inorder
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
recursive subroutine delete_node(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
type(node), pointer :: keep
if (.not. associated(root)) return
if (value < root%value) then
call delete_node(root%left, value)
else if (value > root%value) then
call delete_node(root%right, value)
else if (.not. associated(root%left)) then
keep => root%right
deallocate (root)
root => keep
else if (.not. associated(root%right)) then
keep => root%left
deallocate (root)
root => keep
else
root%value = minimum(root%right)
call delete_node(root%right, root%value)
end if
end subroutine delete_node
integer function minimum(root) result(v)
type(node), pointer, intent(in) :: root
type(node), pointer :: cur
cur => root
do while (associated(cur%left))
cur => cur%left
end do
v = cur%value
end function minimum
recursive subroutine inorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
call inorder(root%left)
write (*, '(i0, 1x)', advance='no') root%value
call inorder(root%right)
end subroutine inorder
end module deletable
program b6
use deletable
implicit none
type(node), pointer :: root => null()
integer :: values(9), i, gone(4)
values = [50, 30, 70, 20, 40, 60, 80, 35, 65]
do i = 1, size(values)
call insert(root, values(i))
end do
gone = [20, 30, 50, 99]
do i = 1, size(gone)
call delete_node(root, gone(i))
if (associated(root)) then
write (*, '(a, i0, a)', advance='no') 'after deleting ', gone(i), ': '
call inorder(root)
print *
else
print '(a, i0, a)', 'after deleting ', gone(i), ': tree is empty'
end if
end do
end program b6
Deleting 20 removes a leaf, deleting 30 replaces it with its only child 35, and deleting 50, the root with two children, takes 60 from the right subtree and makes it the new root value. The missing value 99 changes nothing, which the code guarantees by returning as soon as the pointer is null. The in-order output stays sorted after every step, which is the simplest proof that the links were rewired correctly.
$ gfortran b6.f90 -o b6 $ ./b6 after deleting 20: 30 35 40 50 60 65 70 80 after deleting 30: 35 40 50 60 65 70 80 after deleting 50: 35 40 60 65 70 80 after deleting 99: 35 40 60 65 70 80
Freeing the tree
Every node was allocated separately, so every node must be freed separately. A
post-order walk is the right order: free the left subtree, free the right
subtree, then free the node. The node cannot be freed first, because its
pointers are the only way to reach its children. The routine sets each pointer
to null after deallocating it, so the caller can test the root with
associated and see that the tree is gone.
module owned
implicit none
private
public :: node, insert, free_tree, inorder
type :: node
integer :: value = 0
type(node), pointer :: left => null()
type(node), pointer :: right => null()
end type node
contains
recursive subroutine insert(root, value)
type(node), pointer, intent(inout) :: root
integer, intent(in) :: value
if (.not. associated(root)) then
allocate (root)
root%value = value
else if (value < root%value) then
call insert(root%left, value)
else if (value > root%value) then
call insert(root%right, value)
end if
end subroutine insert
recursive subroutine free_tree(root)
type(node), pointer, intent(inout) :: root
if (.not. associated(root)) return
call free_tree(root%left)
call free_tree(root%right)
deallocate (root)
nullify (root)
end subroutine free_tree
recursive subroutine inorder(root)
type(node), pointer, intent(in) :: root
if (.not. associated(root)) return
call inorder(root%left)
write (*, '(i0, 1x)', advance='no') root%value
call inorder(root%right)
end subroutine inorder
end module owned
program b7
use owned
implicit none
type(node), pointer :: root => null()
integer :: values(7), i
values = [50, 30, 70, 20, 40, 60, 80]
do i = 1, size(values)
call insert(root, values(i))
end do
call inorder(root)
print *
call free_tree(root)
print '(a, l1)', 'root associated after free: ', associated(root)
do i = 1, size(values)
call insert(root, values(i))
end do
print '(a, i0)', 'rebuilt root: ', root%value
call free_tree(root)
print '(a, l1)', 'root associated after second free: ', associated(root)
end program b7
The first walk prints the seven values in order, the free routine returns, and the root is no longer associated. Rebuilding the tree proves that the pointer can be reused, and the second free leaves it null again. A program that forgot this step would leak one small block per node, a leak that matters when a tree is built and discarded inside a loop.
$ gfortran b7.f90 -o b7 $ ./b7 20 30 40 50 60 70 80 root associated after free: F rebuilt root: 50 root associated after second free: F
Next steps
The recursion article explains the mechanics behind every routine here: the base case, the recursive call and the way a result is built on the way back. The pointers article covers the association rules that a node type relies on, and the linked lists, stacks and queues article builds the simpler one-pointer structure that a tree generalises. The sorting article shows what it costs to keep values in order in an array instead, and the derived types article introduces the components and constructors used for the nodes.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have defined a self-referential node with two pointers, inserted values so that the search tree rule holds, walked the tree in pre-, in- and post-order, searched it iteratively, measured its size, height and leaves, listed the smallest and largest values and a range between two limits, deleted leaves and inner nodes, and freed the whole structure. The previous article, Fortran linked lists, stacks and queues, shows the one-pointer node that this article extends.
Author
List all Fortran tutorials.