DFS: pre / in / post
Scenario
You have a 3-line recursive tree function: call left, call right, process node. Simply changing the position of that 1 processing line changes the entire purpose of the algorithm.
Why does moving a single line of code turn tree cloning into tree deletion or sorted sorting?
Why it exists
Problem: Different tree tasks require different information availability. Cloning requires knowing parent values first; deleting or computing tree height requires knowing child results first.
Naive approach: Using a single generic traversal and re-traversing the tree multiple times to gather parent or child data.
Better idea: Select the exact DFS order (pre-order, in-order, or post-order) suited for your data dependency: process parents before children (pre), process between children (in), or process children before parents (post).
Mental model
The three DFS orders are identical recursive journeys; they only differ by when you record the node on your itinerary.
Every DFS traversal traverses the exact same edges in the exact same sequence. Pre-order records a node on first entry (top-down), in-order records it after returning from the left child (left-to-right), and post-order records it after returning from both children (bottom-up).
Repeated decision: do I record this node BEFORE, BETWEEN, or AFTER its two recursive calls?
Explanation
All three Depth-First Search orders execute the exact same recursive structural walk:
1. Recurse Left
2. Recurse Right
The ONLY difference is where the node 'visit' (processing or recording) happens relative to those two calls.
Code Comparison:
- Pre-order:
visit(node)
dfs(node.left)
dfs(node.right)
- In-order:
dfs(node.left)
visit(node)
dfs(node.right)
- Post-order:
dfs(node.left)
dfs(node.right)
visit(node)
The Headline Payoffs:
1. Pre-Order (Top-Down): Useful for cloning or serializing trees. You process the parent before creating or copying its subtrees.
2. In-Order (Sorted Sequence): For a Binary Search Tree (BST), in-order traversal visits values in strictly non-decreasing sorted order.
3. Post-Order (Bottom-Up): Useful for subtree computations (height, diameter, subtree size) and directory deletion (`rm -rf`). You must process and free both child subtrees before you can safely process or delete the parent.
Concrete Walkthrough on BST:
Root `4` with left child `2` (which has left `1`, right `3`) and right child `5`.
Structure:
4
/ \
2 5
/ \
1 3
- Pre-order trace: `4` -> `2` -> `1` -> `3` -> `5`. (Top-down structure preserved).
- In-order trace: `1` -> `2` -> `3` -> `4` -> `5`. (Produces perfectly sorted sequence `[1, 2, 3, 4, 5]`).
- Post-order trace: `1` -> `3` -> `2` -> `5` -> `4`. (Leaves processed first, root processed absolute last).
Key points
- Same Walk, Different Timing: Pre-order visits on entry, in-order visits between children, post-order visits on exit.
- BST In-Order Invariant: In-order traversal of a valid BST ALWAYS yields elements in sorted ascending order.
- Post-Order Bottom-Up Invariant: Post-order guarantees child results are completely calculated before parent logic runs.
Pattern: DFS Traversal Order Selection
Recognition cues:
- top-down dependency (pre-order)
- sorted BST processing (in-order)
- bottom-up aggregation (post-order)
Failure signals
- You need to delete a file directory where subfolders must be emptied before parent folder removal.
- You need to extract sorted elements from a BST.
- You need to serialize a tree into a format that can recreate its exact structure.
Engineering examples
Recursive Directory Deletion (`rm -rf`)
Delete an entire directory tree from disk without leaving orphaned file handles.
Post-order traversal ensures all files and subdirectories inside a directory are deleted before removing the parent directory itself.
Tree Serialization & Deserialization
Convert a binary tree structure into a string to send over a network.
Pre-order traversal records the root first followed by subtrees, allowing easy top-down reconstruction during deserialization.
When not to use
- Finding shortest path in unweighted tree level by level: DFS explores deep paths to leaves first. Use BFS (level-order) to find shallowest target nodes efficiently.
Common mistakes
- Assuming in-order sorts any binary tree: In-order traversal ONLY produces a sorted sequence if the binary tree satisfies the Binary Search Tree (BST) property.
- Believing pre, in, and post-order visit different nodes: They visit the exact same set of nodes and traverse the exact same edges. Only the timing of when the node's action occurs changes.
- Using pre-order when child values are required: Attempting to calculate subtree properties (like tree height) with pre-order leads to repetitive, inefficient top-down re-calculations.
Recall questions
- What order does an in-order traversal of a Binary Search Tree produce?
- Why is post-order traversal used for directory deletion (`rm -rf`)?
- What is the key difference between pre-order and post-order traversal?
Questions & answers
Find the k-th smallest element in a Binary Search Tree.
Perform an in-order traversal (which visits BST nodes in sorted order) and return the k-th visited node.
Approach: In-order DFS traversal yields sorted order; count visits up to k.
Serialize and deserialize a binary tree.
Use pre-order traversal with null indicators to serialize. Reconstruct top-down using the pre-order string.
Approach: Pre-order DFS encodes root before subtrees, allowing unambiguous reconstruction.
Interesting facts
- Post-order traversal is also known as Reverse Polish Notation evaluation when applied to expression trees.
Continue learning
Previous: Binary tree & traversals
Next: Validate a BST
Next: Height & diameter
Related: Binary tree & traversals
Related: Validate a BST
Related: Height & diameter