Binary Trees/Inorder

Notes

The basis of in-order traversal is that the binary tree be sorted. This implements the convention of a sorted binary tree, a recursive definition:

The value of node k is greater than every node in the left subtree of node k. (Left goes first. Left to right precedence.)

The value of node k is less than every node in the right subtree of node k. (Right goes second. Left to right precedence.)

define inorder_traversal( tree ):
    inorder_traversal( tree, root, 0 )

define inorder_traversal( tree, position, depth ):
    inorder_traversal( tree, position.left(), depth+1 );
    // perform visit action on position
    inorder_traversal(tree, position.right(), depth+1 );

Related Pages

Preorder, postorder, and in-order traversals on trees:

• Binary Trees/Inorder
• Trees/Postorder

Breadth-first and depth-first traversals on trees:

• DFS
• BFS

Graphs, generalization of tree structures:

• Graphs#Graph Traversals