Tree Traversal
01 / The one-sentence essence
Every tree-traversal algorithm visits every node exactly once — the only thing that varies is when the visit happens relative to the recursive descent into children.
Problemtraverse a binary tree in a given orderTree[1, 2, 3, 4, 5, ·, 6]Modepreorder
output— nothing yet —
Depth-first — preorder visits the node before recursing into children.
step
0 / 7
visiting
—
visited
0 / 6
mode
preorder
0 / 7
02 / The pattern signature
# depth-first — three variants differ only in where "visit" sitstraverse(node):if node is null: returnvisit(node) // preordertraverse(node.left)visit(node) // inordertraverse(node.right)visit(node) // postorder# breadth-first — iterative, queue-basedlevel_order(root):q ← [root]while q not empty:node ← q.dequeue(); visit(node)enqueue node.left, node.right
03 / When to recognize this pattern
"in-order on a BST"
The sorted output of a binary search tree comes from inorder — that's a property of BSTs, not of inorder in general.
"level by level"
You need to process the tree row by row — node depths, zigzag output, "find the right side of the tree". Level-order via a queue is the tool.
"bottom-up / children-first"
You can't decide a node's answer until its children's answers are known — subtree sums, heights, paths. Postorder guarantees children are visited first.
"serialize / clone"
Producing a string representation of a tree, or copying one node-by-node. Often preorder with explicit null markers — it captures the structure unambiguously.
04 / Common pitfalls
i.
Using inorder when postorder is required.
Anything that needs a child's answer to compute the parent's — subtree sums, heights, diameters — must visit children before the parent. That's postorder. Inorder will visit some children too late.
ii.
Forgetting the null check.
The first line of the recursive traversal is
if node is null: return. Missing it dereferences null at every leaf's missing children. The animation makes this explicit — null subtrees just don't render.iii.
Confusing the call stack with the output list.
The recursion's natural call stack is not the order of visits. A node is on the call stack from before its preorder visit through after its postorder visit — three different "moments" of the same node.
05 / Go practice — on LeetCode
Four problems. The first three are the canonical DFS orders. The fourth lifts you into BFS and is where level-order earns its keep.