Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.f90 
program main
  implicit none
  integer :: value(7), left(7), right(7)
  integer :: queue(8), front, back, output(7), n, id
  character(len=128) :: out
  call setup(value, left, right)
  out = ''
  call render_node(4, value, left, right, out)
  print '(A)', trim(out)
contains
  subroutine setup(value, left, right)
    integer, intent(out) :: value(7), left(7), right(7)
    value = [1,2,3,4,5,6,7]; left = 0; right = 0
    left(4) = 2; right(4) = 6; left(2) = 1; right(2) = 3; left(6) = 5; right(6) = 7
  end subroutine setup
  subroutine append(out, text)
    character(len=*), intent(inout) :: out
    character(len=*), intent(in) :: text
    out = trim(out) // text
  end subroutine append
  recursive subroutine render_node(id, value, left, right, out)
    integer, intent(in) :: id, value(7), left(7), right(7)
    character(len=*), intent(inout) :: out
    character(len=16) :: buf
    if (id == 0) then; call append(out, '_'); return; end if
    write(buf, '(I0)') value(id); call append(out, trim(buf))
    if (left(id) /= 0 .or. right(id) /= 0) then
      call append(out, '('); call render_node(left(id), value, left, right, out); call append(out, ',')
      call render_node(right(id), value, left, right, out); call append(out, ')')
    end if
  end subroutine render_node
  recursive subroutine preorder(id, value, left, right, output, n)
    integer, intent(in) :: id, value(7), left(7), right(7)
    integer, intent(inout) :: output(7), n
    if (id == 0) return
    n = n + 1; output(n) = value(id)
    call preorder(left(id), value, left, right, output, n)
    call preorder(right(id), value, left, right, output, n)
  end subroutine preorder
  subroutine print_list(output, n)
    integer, intent(in) :: output(7), n
    integer :: i
    write(*, '(A)', advance='no') '['
    do i = 1, n
      if (i > 1) write(*, '(A)', advance='no') ', '
      write(*, '(I0)', advance='no') output(i)
    end do
    print '(A)', ']'
  end subroutine print_list
  logical function search_value(id, target, value, left, right)
    integer, intent(in) :: id, target, value(7), left(7), right(7)
    integer :: cur
    cur = id
    do while (cur /= 0)
      if (target == value(cur)) then; search_value = .true.; return; end if
      if (target < value(cur)) then; cur = left(cur); else; cur = right(cur); end if
    end do
    search_value = .false.
  end function search_value
end program main

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The executable builds the canonical balanced tree. The replay also includes a sorted-order contrast where height grows to 4, showing why an unbalanced BST can degrade to O(n) without rotation.
binary search tree Values smaller than a node go left; larger values go right.