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.

            30
           /  \
          /    \
         /      \
        /        \
       12        64
      /  \      /   
     /    \    /
    8     14  50
   /     /  \
  5    13   20

void visit(struct node * current)
{
  visit(current->left);
  print(current->value);
  visit(current->right);
}

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.