Binary tree traversal

Binary tree traversal is visiting every node in a Binary tree exactly once. There are four standard orders, each with its own atomic note:

• Pre-order traversal — Root, Left, Right. Use for tree copying, prefix output.
• In-order traversal — Left, Root, Right. Use for BST sorted output.
• Post-order traversal — Left, Right, Root. Use for tree deletion, postfix output, recursive metrics.
• Level-order traversal — by depth, left to right. Use for shortest paths, layer-by-layer processing.

The first three (pre/in/post) are depth-first: they walk down one subtree to its leaves before backing up. They differ only in when the current node is processed relative to its left and right subtrees. All three use a stack — explicit or the call stack — and run in $O(h)$ space where $h$ is tree height.

Level-order is breadth-first: it processes nodes by depth using a Queue. Structurally different; uses $O(w)$ space where $w$ is the widest level.

Quick comparison

Order	Sequence	Driver	Space	Sample use
Pre-order	Root, Left, Right	Stack	$O(h)$	Tree copy, prefix expression
In-order	Left, Root, Right	Stack	$O(h)$	BST sorted output
Post-order	Left, Right, Root	Stack	$O(h)$	Tree deletion, postfix, recursive metrics
Level-order	By depth, left-to-right	Queue	$O(w)$	Shortest paths, layer processing

All four are $O(n)$ time — every node is visited exactly once.

Worked example tree

For consistency across the four child notes, the same tree is used in each:

            7
          /   \
        12     15
        / \    /
       -2 22  -19

Order	Output
Pre-order	7 12 -2 22 15 -19
In-order	-2 12 22 7 -19 15
Post-order	-2 22 12 -19 15 7
Level-order	7 12 15 -2 22 -19

(In-order’s output isn’t sorted because the tree isn’t a BST. On a BST, in-order does give sorted output — that’s its defining property.)

Picking an order

If you need…

• The parent before the children → pre-order.
• The values in sorted order from a BST → in-order.
• The children before the parent (deletion, computing parent value from child results) → post-order.
• Layer-by-layer / shortest-path-from-root semantics → level-order.

Generalisation to graphs

Tree traversals generalise directly to graph traversals — you just need a “visited” set to avoid revisiting nodes on cycles. The depth-first family becomes Depth-first search (DFS); level-order becomes Breadth-first search (BFS). Trees have no cycles, so the visited set is unnecessary for the tree cases above — but show up the moment you traverse a general graph.