Crossings: pre in post

Three depth traversal orders are common. One starts at the node and then visits the left and right subtrees. Another visits the left subtree first, then the node, and then the right. The third concludes the node only after both subtrees.

For a search tree, the left-node-right order yields the sorted key sequence. The node-first order is suitable for serializing the structure.

Example tree: root 2, left 1, right 3. The sorted traversal results in 1, 2, 3.

Inorder as a sequence: Binary Tree Inorder Traversal [1].

Where used

Serialization before children, sorted output in search trees, expression evaluation, and releasing after children, build systems, and dependency resolution. The choice of traversal order is a product decision, not just an exercise.

Depth

Depth traversals differ by the time the current node is processed relative to its subtrees. Processing before both children is suitable for serializing structure, processing between children yields sorted keys in search trees, and processing after both children supports bottom-up evaluations.

All three variants visit every reachable node once and require time proportional to the number of nodes. The additional storage depends on the height, because at most one root path needs to be active at the same time.

An iterative implementation stores nodes together with the state yet to be executed. Simply storing nodes is often not sufficient for variants processing after one child.

Difficulty levels

1. Determine traversal orders for a small tree.
2. Choose the processing time based on an application goal.
3. Iteratively represent recursive control states.

Pitfalls

The order of values does not always determine the tree uniquely without additional information. In the iterative form, children are often stored in the wrong order.