Recursion in tree traversal

Question

I'm new to the concept of graphs and trees.Below is the inorder tree traversal of tree.

 if(n!=null){
     treeTraversal(n.left);
     System.out.println(n.val);
     treeTraversal(n.right);
 }

I'm not able to understand the flow as it involves recursion. Can somebody explain me how does control flow takes place with respect to stack.

Answer 1

Let's say I have a tree which is something like:

    4
   / \
  2   5
 / \
1   3

Your code will first put the recurse through the left children 4 -> 2 -> 1. Since 1 does not have a left child (it is null), it will print 1 and then pop the stack. Next up in the recursion is 2. It will print 2 then traverse the right child of 2 i.e 3. It will print 3, then pop the stack. Then it will print 4, then 4's right child 5. The sequence of prints will be 1, 2, 3, 4, 5. Here is a good animation too.