Need help fixing a Fortran recursive subroutine that is only assigning values and inserting nodes to the left in a binary tree

I am struggeling with this:

I want to

create a head node with a left and right child
derive different values from the head node and assign one of them to the left, other to the right
then work with the assigned values of the right and left child: derive a new value from the left(right) childs value and create 2 new children of the left(right) one and assign the derived values ... continue in this matter so in the next step I would have 4 nodes to work with and so on...

(I need a recursive approach)

How can I fix the problem, that my program is only assigning values and inserting notes to the left? I know WHY it's not working. I just dont know what else to do.

How can i make it possible, that after inserting/assigning on the left, it heads to the right child and does the same thing all the time and not only in the first recursion?

Thank you so much in advance! Let me know if I need to specify anything.

EDIT: the input string will be an expression of the form ((3*(4+7)):((4+2)*(3-1))) for example. (the outer brackets will always be there)

Here is what I tried:

recursive subroutine split(str)

    character(len=80):: str
    type(tree),pointer:: point
  

    allocate(point)

    point%expression = str


    call find_bracket(point%expression)
       
    if(found_bracket) then           !it searches for a ")" bracket

        allocate(point%left)
        allocate(point%right)

        call find_zero_niveau(str)  
        call empty_slots(str)


        point%left%expression = str(2 : zero_niv - 2)                !assigning the new values
        point%right%expression = str(zero_niv  : 80 - spaces - 1)
        point%expression = str(zero_niv - 1 : zero_niv - 1 )


            point => point%left
         
            call split(point%expression)

        
            point => point%right            
          
            call split(point%expression)          ! this obviously will not work

    end if 


end subroutine split

tree is defined like this:

 type tree
        character(len=80)::expression
        type(tree), pointer::left,right
 end type tree

    subroutine find_zero_niveau(str)

        character(len=80)::str
        integer::j, bracket_niv
        logical::bracket_check = .false.

        call empty_slots(str)



        j = 80 - spaces                     
        bracket_niv = 0


        do while (j >= 1)  
                   
            j = j - 1

            call getnextchar(str,j)

            if (next_char == ")") then
                bracket_check = .true.
                bracket_niv = bracket_niv + 1
           
            else if (next_char == "(") then
               
                bracket_niv = bracket_niv - 1

            end if


            if (bracket_niv == 0 .and. bracket_check) then
                
                zero_niv = j
               
                exit

            end if
            
        end do

    end subroutine find_zero_niveau


   subroutine empty_slots(str)

        character(len=80)::str
        integer::i 

        spaces = 0

        do i=1,80

            call getnextchar(str,i) !getnextchar just extracts a value from the string

            if (next_char == " ") then
                spaces = spaces + 1

            else if (next_char /= " ") then
                spaces = 0

            end if

        end do

    end subroutine empty_slots

Solution

As I said in a commment, I can't see how your routine could create a tree at all. At each call you are creating and allocating a point variable, which is local and therefore destroyed once the routine returns. The current node of the tree should be passed as an argument to the routine, and you should have the following structure:

recursive subroutine split(point)
    implicit none
    type(tree), intent(inout) :: point

    call find_bracket(point%expression)

    if(found_bracket) then 
        call find_zero_niveau(point%expression)  
        call empty_slots(point%expression)

        allocate(point%left)
        point%left%expression = str(2 : zero_niv - 2)
        call split(point%left)
       
        allocate(point%right)
        point%right%expression = str(zero_niv  : 80 - spaces - 1)
        call split(point%right) 

        point%expression = point%expression(zero_niv - 1 : zero_niv - 1 )
    end if 
end subroutine split

The head of the tree should be created before the first call:

type(tree), pointer :: head
allocate(head) 
head%expression = initial_expression
call split(head)

More generally it seems that you are using many global variables, which is highly error-prone when dealing with recursive routines. Pass the variables as arguments as much as possible, and do not use global variables unless you have a good reason to do so.

Finally, you may replace all the pointer attributes by allocatable attributes. The advantage is that allocatable components are automatically deallocated when going out of scope, for instance here to destroy the tree you would just have to deallocate the head and all the nodes would be automatically and recursively deallocated. In the case you want to keep pointers, you should initialize them in the type description:

 type tree
        character(len=80) :: expression
        type(tree), pointer :: left  => null(), &
                               right => null()
 end type tree