Inorder traversal

In Computer science, Inorder traversal is used in Data structures, and specifically, Trees and Binary Trees.

Programs that utilize tree strucutres need to process nodes in a tree (represented as circles in below diagram). Nodes contain information about an object. For now, let's assume each node contains a letter. The arrows indicate a link between nodes.

InOrder Traversal is a type of Tree Traversal algorithm. Inorder refers to when the root is processed inbetween to its two subtrees.

Steps to Inorder Traversal

Given a non-empty tree,

Process the nodes in the left subtree with a recursive call
Process the root
Process the nodes in the right subtree with a recursive call

Given a binary tree PY:

File:TreePY.gif

The order would go D,B,G,E,A,C,F

Here is an example of InOrder in C++

template <class Item>
int inorder_print(const binary_tree_nodes<Item>* ptr)
// ptr is a pointer to a node in a binary tree OR null
// meaning empty tree.
{
   if (ptr != NULL)
   {
       inorder_print( ptr->left() );
       std::cout << ptr->data() << std::endl;
       inorder_print( ptr->right() );
   }
   return 0;
}

Compare: Pre-order traversal, post-order traversal