Binary Tree Recursive InOrder method confusion

Question

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 would recursively call printInorder(node.left) until it reached 20.

At that point, it would then print "20 ", then it checks printInorder(node.right), sees that it is null and returns back to the printInorder(node.right) statement, at which point it is at the bottom of the method and has no more code to run so it exits.

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, LITERALLY step-by-step for me? Please pretend you are explaining it to someone with a mental impediment. Thank you.

Answer 1

There is this joke "To understand recursion one should first understand recursion"

First lets look at the function. What does it do?

• Checks if there is a left node and if there is goes there (without printing yet)

• If there is no left node prints

• checks if there is a right node and goes there.

So the execution here.

1. 1st execution of printInorder(50) Checks if has left - goes to the left node (printing waits)
2. 2nd execution now with the left node printInorder(40) Checks if has left node - yes it does! Go to the left an wait with the print
3. 3rd execution with left node printInorder(20) Does it have a left node? No! Calls printInorder(null) and continues the execution. Now 20 is printed! Does it have right node? No
4. We go back! to step 2 where we had printinorder(40) but now we are at the point AFTER going to the leftNode. So we print that 40 and check for right node - voila 45 is found!
5. Go to 45 and check if has left node (printing 45 waits). Left node is 43
6. Goes to printinorder(43) and since it has no left prints it!

and so it goes...