Thread: Java Recursion, Need help confused

I am working on a Red Black tree for a data structures class.

I have the code:

void printInorder(Node node)    //Input is initially the root node 
{ 
     if (node == null) 
     { 
           return; 
     } 
     printInorder(node.left); 
     System.out.println(node.data); 
     printInorder(node.right); 
}

Let's use this Binary tree as an example:

             50 
           /    \ 
         40     60 
       /    \       \ 
      20    45      70 
         /   \      / 
          43  47  65

The output of the code is correct and is : 20 40 43 45 47 50 60 65 70

My understanding of the code is that it goes from 50 --> 40 --> 20 and then sees that it is pointing to null. It returns to the printInorder(node.left) that passed in the null. It prints out the 20. Then, it checks the right and sees that is also null and returns to the printInorder(node.right). Now that it has returned to the printInorder(node.right), it will continue to the next line of code, but since there is no more code it will cease running the method.

The output is correct, but from my understanding of the code it should stop after printing "20".

Can someone explain the process of this recursive loop, step-by-step for me? Thank you.

This is tricky because the location of the print statement is such that it does not reflect where the processing is at any given time. The first call is looking at the "50" node, but the first print statement is "20" because it calls down the left side multiple times first before printing anything. Move the print statement to the beginning of the function if you want to follow where it actually goes in the execution. Hopefully that'll clean up some of the noise and help it make more sense.