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.)

// public inorder_traversal method:

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


// protected/private recursive inorder_traversal method:
// (note, visit() function is the action being performed on the tree node)

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

Related Pages

Graphs:

• Graphs#Graph Traversals
• Graphs/Depth First Traversal
• Graphs/Breadth First Traversal
• Graphs/Euler Tour
• Graphs/Euler Circuit

Traversals on trees:

• Trees/Preorder
• Trees/Postorder
• Trees/Inorder

Breadth-first search and traversal on trees:

• BFS - breadth first search
• BFT - breadth first traversal

Depth-first search and traversal on trees:

• DFS - depth first search
• DFT - depth first traversal

OOP design patterns:

• Tree Traversal/Traversal Method Template

Category:Traversal