How does this inorder traversal algorithm work?

Question

I don't have much experience with recursion, so I'm having a hard time determining exactly how this algorithm works:

 public static void inorder(Node<?> n)
 {
  if (n != null)
  {
   inorder(n.getLeft());
   System.out.print(n.data + " ");
   inorder(n.getRight());
  }
 }

I know that it visits the left and right child nodes of every node in the tree, but I just can't get my head around why exactly it works.

Answer 1

I'll try to give it a shot.

Imagine a tree

           a
      b          c
   d    e     f     g

Each letter represents a Node object.

What happens when you pass in the 'a' node is that it will look at the first left node and find 'b'. It will then call the same method on 'b' and wait until that returns

In 'b' it will look for the first left node and find 'd'. It will then call the same method on 'd' and wait until that returns

In 'd' it will look for the first left node and run the same method. Since the left node is null the function will return. It will then print out 'd' After it prints out 'd' it will call the function on the right node to 'd' which is also null and immediately return. Then that instance of the method will return back to the 'b' node function.

It will now print out 'b' then call the method on the right hand node of 'b'.

It will find node 'e' Then it will call the method on the left node of e which will be null and return. Then print out 'e'. then call the method on the right node of 'e' which is also null and return back to the 'e' method call. Then it will return out to the 'b' node.

From 'b' it will return back up to 'a', print out 'a' and start the same process on the right side of 'a'.

Eventually it will print out:

d b e a f c g