Depth-first: pre, in, post-order

Depth-first traversal commits to one branch and follows it to the bottom before backing up. All three depth-first orders make the same two recursive calls — left subtree, right subtree — and differ only in when they visit the node: before the calls (pre-order), between them (in-order), or after them (post-order). On a binary search tree, in-order comes out sorted, for free.

The badge on each node is its visit number for the selected order. Watch the root move from first, to fourth, to last as you switch pre → in → post.

When you visit the node Advanced: traversal as a fold

When you visit the node

Pre-order records the node, then recurses left then right. In-order recurses left, records the node, then recurses right. Post-order recurses both subtrees first and records the node last. Select an order and read the visit numbers and the resulting sequence.

The order · select one

clause: visit(v); pre(l); pre(r)

sequence: 12 · 8 · 5 · 10 · 30 · 20 · 42

Same shape, same two recursive calls, three results — because the only choice is where the visit sits relative to the recursion. Pre-order copies or serialises a tree; in-order reads a BST in sorted order; post-order frees or evaluates children before their parent.

Advanced: traversal as a fold

All three orders are special cases of one higher-order function: a tree fold that threads an accumulator through the node and its subtrees. Place the fun call before the recursive calls and you have pre-order; between them, in-order; after them, post-order. Folding a BST in-order with [v | acc] and reversing yields a sorted list — no separate sort needed, because the BST invariant already ordered the keys.

The recursive version uses the call stack, which is fine for balanced trees (depth log n) but risky for a degenerate one. When depth is unbounded, swap the implicit stack for an explicit one: push the right child, then the node, then the left child, and pop until empty — the same traversal as a loop.

# one fold, parameterised by where the node is visited
def reduce(nil, acc, _f), do: acc
def reduce({v, l, r}, acc, f) do
  acc = reduce(l, acc, f)     # left subtree first…
  acc = f.(v, acc)            # …visit here ⇒ in-order
  reduce(r, acc, f)            # …then the right subtree
end

# in-order of a BST is sorted, so this needs no Enum.sort:
tree |> reduce([], fn v, acc -> [v | acc] end) |> Enum.reverse()
# => [5, 8, 10, 12, 20, 30, 42]

The idea

Depth-first is one recursion; the order is only where you place the visit among the two recursive calls.

In Elixir

visit before / between / after reduce(l) and reduce(r) gives pre / in / post.

Next: breadth-first & balance — the other way to walk a tree, and what keeps the descent at log n.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Tree traversal — Wikipedia — depth-first and breadth-first orders.
Okasaki, C. (1996). Purely Functional Data Structures. — trees, functionally.