InOrder Traversal

It traverses the left subtree, then visits the parent node, and after that visits the right subtree. For example:

336px-Sorted_binary_tree_inorder.svg

 

InOrder: A, B, C, D, E, F, G, H, I

Recursive Algorithm

inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)

Iterative Algorithm

Inorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right