In-order traversal
In-order traversal is a method for visiting all nodes of a binary search 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 the node itself. See the article binary search tree for an explanation on why this is always so.
In C, the algorithm for in-order traversal of a binary tree looks like this:
void visit(struct node * current)
{
visit(current->left);
print(current->value);
visit(current->right);
}
Its function is described by this flowchart:
File:In order traversal algo.jpg
Note that the tests that has to be made to ensure that the right and left children exists is omitted in the C-code but included in the flowchart.
An example
With in-order traversal, starting at the root node (30), the visit() procedure would print: 5, 8, 12, 13, 14, 20, 30, 50, 64. If the call to print() instead would have been the first statement, the output would have been: 30, 12, 8, 5, 14, 13, 20, 64, 50. The "route" the recursive procedure would take looks like this:
