inorder traversal

Inorder traversal is a method for visiting all nodes of a binary tree. It's not depth-first (that would be postorder traversal), and it's not breadth-first either.

Inorder traversal visits the left subtree first (with inorder traversal, naturally), then the root, then the right subtree. The naïve implementation uses recursion; more efficient ways include various "tree threading" techniques or pointer reversal.

Note that this method applies only to binary trees, not even to trees! Every child must be either a "left child" or a "right child" of its parent, or we won't know whether to traverse it before or after its parent.

In a binary tree which is the parse tree of an arithmetical expression, in-order traversal corresponds (if brackets are added either everywhere or appropriately) to the regular infix notation.

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

           C     depth = 0
          / \
         B   E   depth = 1
        /   / \
       A   D   F depth = 2