In-order traversal

In-order traversal is a method for visiting all nodes of a binary tree in either increasing or decreasing order. In in-order traversal, the left subtree of every node is always visited first. So if you begin with the root node, its left subtree will be visited first, then the root node itself and last, the right subtree.

This method works because of the fact that for every node in the tree: all nodes in its left subtree has a lower value than the node itself, and all nodes in its right subtree has a greater value than itself.

      4
     / \
    /   \
   3    12

The in-order traversal of a Binary Search Tree always results in a sorted ( and that too increasing ) list of elements. In in-order traversal, the left subtree of every node is visited first. So if you take the example of the root, its left subtree will be visited first, then the root will be visited and then its right subtree will be visited.

Procedure IN_ORDER_TRAVERSAL(G) {

 IN_ORDER_TRAVERSAL(left[G])
 print key[G]
 IN_ORDER_TRAVERSAL(right[G])

}

The above code recursively in-order traverses the Graph G.