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

Answer 2

The best way to understand recurssion is try to state your problem verbally and then work through an example (You can refer @Mark Carpenter 's example) :

The way inorder search works is as follows :

Say I am at node n :

1) First access all nodes to left of node n. (i.e n.getLeft()) in inorder fashion , the best way to achieve this is to call inorder() recursively and pass it the left child of n.

2) Now when the function reaches this step, it had already printed all left children of Node n. So now print Node n.

3) Now access all nodes to right of node x. (i.e n.getRight()) in inorder fashion, the best way to achieve this is to call inorder() recursively and pass it the right child of n.

Answer 3

Until you get used to recursion, it seems amazing that a little code can accomplish so much. In this case, you should try going through the algorithm by hand on an actual tree to see what happens.

In the tree below from Wikipedia, you can see an in-order traversal that prints out A, B, C, D, E, F, G, H, I.

1. It starts at F and calls inorder on the leftmost Node.
2. It then calls inorder on B, and then calls inorder on A.
3. A gets printed and then the Algorithm continues where it was in the previous call on B...

(See more on my Tree Traversal Tutorial.)