Tree traversals - Inorder Traversal

        A binary tree can be traversed in two ways.
i) Depth First Traversal: Inorder, preorder, postorder
ii) Breadth First Traversal: Level Order Traversal

Inorder traversal: 
     In inorder traversal root is visited in between left and right subtree traversals.

Steps:
1. Traverse the left subtree
2. Visit the root
3. Traverse the right subtree

Note: If binary search tree is traversed in inorder, the numbers will be sorted in ascending order.

Code:

void inOrder(Node root) {
    if(root==null)
        return;
    inOrder(root.left);
    System.out.print(root.data+" ");
    inOrder(root.right);

}

Illustration:

Inorder traversal of given tree is 3, 5, 4, 7, 8


 Consider the left subtree of 7 (since 7 is the root ,we always start our traversal from root)




Here we start form 5, the left subtree of 5 is 3. For 3 the left subtree is empty , So we visit the root. The right subtree of tree is also empty. At this we finished traversing the left subtree of 5.




Now we visit the root i.e, 5





Now we visit the right subtree of 5, i.e 4. Left subtree of 4 is null. So we visit 4. Right subtree of 4 is null. 





 Now we have traversed the left subtree of 7



 Visit root i.e, 7



 Consider the right subtree of 7



 Left subtree of 8 is null. So we visit 8. Right subtree is also null. With this we finished traversing the given tree :)