"Walking a tree is just deciding WHEN to do the work: before the children, between them, after them, or one whole level at a time. Four timings, four traversals, and each one is the right tool for a different job."
The Three Depth-First Orders
For a binary tree, the depth-first traversals differ only in when you visit the node relative to recursing into its children:
Pre-order (node → left → right): visit the node before its children. Use it to copy or serialize a tree, or print a structure top-down — you handle a parent before its descendants.
In-order (left → node → right): visit the node between its subtrees. On a binary search tree, this emits keys in sorted order — the single most useful traversal fact in this track.
Post-order (left → right → node): visit the node after its children. Use it when a node's result depends on its children's results — computing sizes/heights bottom-up, freeing/deleting a tree (children first), evaluating an expression tree.
All three are three lines of recursion; the only thing that moves is where you put the "visit this node" line relative to the two recursive calls.
The Fourth: Level-Order (BFS)
Level-order traversal visits nodes by depth — the root, then everything at depth 1, then depth 2 — sweeping the tree in horizontal layers. And it's not recursive: it uses a queue, exactly the breadth-first machinery from the Stacks & Queues track. Dequeue a node, visit it, enqueue its children, repeat. Use it to print a tree level by level, or to find the shallowest node matching some condition (the fewest steps from the root). The depth-first orders use a stack (or the call stack); level-order uses a queue — the same duality you already learned, applied to trees.
Pre/in/post-order differ only in when you visit the node (before / between / after its children) — all recursive, all stack-based. Level-order visits by depth using a queue (BFS). In-order on a BST yields sorted keys; post-order suits bottom-up work.
Choosing the Right Walk
The traversal isn't arbitrary — each matches a need. Need the values sorted? In-order on a BST. Need to process parents before children (serialize, copy)? Pre-order. Need children's answers before the parent's (sizes, deletion, expression evaluation)? Post-order. Need nearest-to-the-root or level-by-level? Level-order with a queue. When a tree problem stumps you, asking "which traversal does this want?" is often the whole solution.
Pippa's Confession
I memorized pre/in/post-order as three separate algorithms and constantly mixed them up. Dad collapsed them to one question: "When do you touch the node — before, between, or after the kids?" One recursion skeleton, one line that slides. And the day I realized in-order on a BST falls out sorted, for free, just from left-node-right — that was the moment trees stopped feeling like rote and started feeling like they were built on purpose.
Code
All four traversals (note: in-order is sorted)·python
from collections import deque
class Node:
def __init__(self, v, l=None, r=None): self.v=v; self.left=l; self.right=r
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7 (a binary SEARCH tree)
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
def pre(n): return [] if n is None else [n.v] + pre(n.left) + pre(n.right)
def ino(n): return [] if n is None else ino(n.left) + [n.v] + ino(n.right)
def post(n): return [] if n is None else post(n.left) + post(n.right) + [n.v]
def level(root): # BFS with a QUEUE
out, q = [], deque([root])
while q:
n = q.popleft(); out.append(n.v)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
return out
print("pre :", pre(root)) # [4, 2, 1, 3, 6, 5, 7] — node before children
print("in :", ino(root)) # [1, 2, 3, 4, 5, 6, 7] — SORTED! (BST + in-order)
print("post :", post(root)) # [1, 3, 2, 5, 7, 6, 4] — children before node
print("level:", level(root)) # [4, 2, 6, 1, 3, 5, 7] — by depth, via queue
For the tree with root 1, left child 2 (whose children are 4 and 5), right child 3: write the pre-order, in-order, post-order, and level-order outputs by hand. Then say which traversal you'd use to safely delete the whole tree (freeing each node only after its children), and why that ordering matters.
Hint
Pre: 1 2 4 5 3. In: 4 2 5 1 3. Post: 4 5 2 3 1. Level: 1 2 3 4 5. Use POST-order to delete — you must free children before the parent, or you'd lose the references to reach them.
Progress
Progress is local-only — sign in to sync across devices.