Loading learning content...
DFS doesn't just visit vertices—it visits them in a structured way that produces two distinct, meaningful orderings: pre-order (when a vertex is first discovered) and post-order (when we're finished exploring all its descendants).
These aren't just theoretical curiosities. Pre-order and post-order are the keys to powerful applications:
Understanding when each ordering occurs—and why—transforms DFS from a simple traversal technique into a powerful analytical tool.
This page provides complete mastery of pre-order and post-order traversals. You'll understand exactly when each ordering is produced, how to implement both in recursive and iterative DFS, and why these orderings matter for advanced algorithms. You'll gain the foundation for topological sorting, cycle detection, and SCC algorithms.
Before diving into pre-order and post-order, we need to understand the two fundamental timestamps DFS assigns to each vertex.
Discovery Time (d[v]): When vertex v is first encountered (pushed onto the stack, begins processing)
Finish Time (f[v]): When we're completely done with vertex v (all descendants explored, about to pop)
These times capture the structure of the DFS exploration:
DFS(v):
d[v] = ++time # Discovery: entering v
# ... explore all descendants of v ...
f[v] = ++time # Finish: leaving v
The Parenthesis Theorem
For any two vertices u and v, their discovery/finish intervals follow a strict nesting rule:
Think of it like matching parentheses: ((( ))) or ( ) ( ), but never ( ( ) ) ( (overlapping/interleaved).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
def dfs_with_timestamps(graph, start_vertices): """ Perform DFS tracking discovery and finish times. Args: graph: Adjacency list {vertex: [neighbors]} start_vertices: List of vertices to start DFS from Returns: Dictionary mapping each vertex to (discovery_time, finish_time) """ time = [0] # Mutable container for global time counter timestamps = {} visited = set() def dfs(v): time[0] += 1 discovery = time[0] visited.add(v) # Explore all descendants for neighbor in graph.get(v, []): if neighbor not in visited: dfs(neighbor) time[0] += 1 finish = time[0] timestamps[v] = (discovery, finish) # Start DFS from each unvisited start vertex for start in start_vertices: if start not in visited: dfs(start) return timestamps def visualize_timestamps(graph, timestamps): """ Create a visual representation of discovery/finish intervals. """ max_time = max(f for d, f in timestamps.values()) print("Vertex Intervals (Discovery → Finish):") print("-" * 60) # Sort by discovery time for clearer visualization sorted_vertices = sorted(timestamps.keys(), key=lambda v: timestamps[v][0]) for v in sorted_vertices: d, f = timestamps[v] # Create visual bar before = "." * (d - 1) interval = "=" * (f - d + 1) after = "." * (max_time - f) print(f" {v}: {before}[{interval}]{after} d={d}, f={f}") print("-" * 60) print(" Time: " + "".join(str(i % 10) for i in range(1, max_time + 1))) # Example: Tree structuretree = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []} timestamps = dfs_with_timestamps(tree, ['A'])visualize_timestamps(tree, timestamps) # Output:# Vertex Intervals (Discovery → Finish):# ------------------------------------------------------------# A: [==============] d=1, f=12# B: .[========].... d=2, f=7# D: ..[==]......... d=3, f=4# E: ....[==]....... d=5, f=6# C: ........[====]. d=8, f=11# F: .........[==].. d=9, f=10# ------------------------------------------------------------# Time: 123456789012## Notice: Each interval is either completely nested or completely disjointReading the Intervals:
Looking at the output:
A: [1, 12] contains all other intervals — A is the root, ancestor of allB: [2, 7] is nested inside A's interval — B is a descendant of AD: [3, 4] and E: [5, 6] are both inside B's interval, disjoint from each other — siblingsC: [8, 11] and B: [2, 7] are disjoint — siblings under AWhy This Matters:
The parenthesis structure reveals the DFS tree:
Pre-order traversal lists vertices in the order they are discovered — when we first reach them, before exploring their descendants.
Definition: A vertex v appears in pre-order at its discovery time d[v].
In recursive DFS:
def dfs(v):
preorder.append(v) # Pre-order: process BEFORE children
for child in children(v):
dfs(child)
Characteristic: A parent always appears before all of its descendants in pre-order.
Pre-Order Properties:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
def preorder_recursive(graph, start): """ Generate pre-order traversal using recursive DFS. Pre-order: Process vertex BEFORE exploring children. """ visited = set() preorder = [] def dfs(v): visited.add(v) preorder.append(v) # PRE-ORDER: Before children for neighbor in graph.get(v, []): if neighbor not in visited: dfs(neighbor) dfs(start) return preorder def preorder_iterative(graph, start): """ Generate pre-order traversal using iterative DFS. In iterative DFS, pre-order is natural: append when popping. """ visited = set() stack = [start] preorder = [] while stack: vertex = stack.pop() if vertex in visited: continue visited.add(vertex) preorder.append(vertex) # PRE-ORDER: When first visiting # Push neighbors in reverse for consistent order for neighbor in reversed(graph.get(vertex, [])): if neighbor not in visited: stack.append(neighbor) return preorder # Example with a treetree = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G'], 'D': [], 'E': [], 'F': [], 'G': []} print("Tree structure:")print(" A")print(" / \\")print(" B C")print(" / \\ / \\")print(" D E F G")print()print(f"Pre-order (recursive): {preorder_recursive(tree, 'A')}")print(f"Pre-order (iterative): {preorder_iterative(tree, 'A')}") # Output:# Pre-order (recursive): ['A', 'B', 'D', 'E', 'C', 'F', 'G']# Pre-order (iterative): ['A', 'B', 'D', 'E', 'C', 'F', 'G']## Notice: Parent (A) before children (B, C)# B before its children (D, E)# Complete subtree of B before moving to CWhen to Use Pre-Order:
Copying/cloning a tree structure: Process parent before children to create structure top-down
Serializing a tree: Pre-order with null markers can uniquely represent a tree
Directory listing (top-down): Show folder before its contents
Prefix expression (Polish notation): Operators before operands
Checking if path exists: In some scenarios, we need to know the path taken to reach a node
The Mental Model:
Think of pre-order as the arrival sequence — the order in which a traveler first arrives at each location during their journey.
Post-order traversal lists vertices in the order they are finished — after all of their descendants have been completely explored.
Definition: A vertex v appears in post-order at its finish time f[v].
In recursive DFS:
def dfs(v):
for child in children(v):
dfs(child)
postorder.append(v) # Post-order: process AFTER children
Characteristic: All descendants appear before their ancestors in post-order.
Post-Order Properties:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
def postorder_recursive(graph, start): """ Generate post-order traversal using recursive DFS. Post-order: Process vertex AFTER exploring all children. """ visited = set() postorder = [] def dfs(v): visited.add(v) for neighbor in graph.get(v, []): if neighbor not in visited: dfs(neighbor) postorder.append(v) # POST-ORDER: After children dfs(start) return postorder def postorder_iterative(graph, start): """ Generate post-order traversal using iterative DFS. Post-order in iterative DFS requires tracking state: we need to know when all children have been processed. """ visited = set() stack = [(start, False)] # (vertex, all_children_processed?) postorder = [] while stack: vertex, processed = stack.pop() if processed: # All children done - now process this vertex postorder.append(vertex) continue if vertex in visited: continue visited.add(vertex) # Push this vertex again with processed=True # It will be processed after all children complete stack.append((vertex, True)) # Push all unvisited children for neighbor in reversed(graph.get(vertex, [])): if neighbor not in visited: stack.append((neighbor, False)) return postorder # Alternative: Using two stacks (simpler for some)def postorder_two_stacks(graph, start): """ Post-order using two stacks. Stack1: Standard DFS Stack2: Collects vertices in reverse post-order Final result: Reverse of Stack2 """ visited = set() stack1 = [start] stack2 = [] while stack1: vertex = stack1.pop() if vertex in visited: continue visited.add(vertex) stack2.append(vertex) # Will be reversed at end for neighbor in graph.get(vertex, []): if neighbor not in visited: stack1.append(neighbor) # Reverse to get post-order return stack2[::-1] # Example with a treetree = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G'], 'D': [], 'E': [], 'F': [], 'G': []} print("Tree structure:")print(" A")print(" / \\")print(" B C")print(" / \\ / \\")print(" D E F G")print()print(f"Post-order (recursive): {postorder_recursive(tree, 'A')}")print(f"Post-order (iterative): {postorder_iterative(tree, 'A')}")print(f"Post-order (two stacks): {postorder_two_stacks(tree, 'A')}") # Output:# Post-order (recursive): ['D', 'E', 'B', 'F', 'G', 'C', 'A']# Post-order (iterative): ['D', 'E', 'B', 'F', 'G', 'C', 'A']# Post-order (two stacks): ['D', 'E', 'B', 'F', 'G', 'C', 'A']## Notice: Children (D, E) before parent (B)# B's subtree complete before C's subtree# Root (A) is lastThe two-stack method works because: (1) Stack2 naturally gets vertices in reverse post-order (parents before children), (2) Reversing Stack2 gives post-order. This is often simpler than managing state flags, though it uses O(V) extra space.
When to Use Post-Order:
Deleting a tree: Delete children before parent to avoid dangling references
Expression evaluation: Evaluate operands before operators (postfix notation)
Topological sorting: Reverse post-order gives a valid topological order for DAGs
Dependency resolution: Process dependencies before dependents
Strongly Connected Components: Kosaraju's algorithm uses post-order
Computing subtree properties: Sum of subtree, height of subtree, etc. — children computed first
The Mental Model:
Think of post-order as the departure sequence — the order in which a traveler leaves each location for the last time, having fully explored everything accessible from there.
Pre-order and post-order are two sides of the same DFS traversal. Understanding their relationship is key to using them effectively.
| Aspect | Pre-Order | Post-Order |
|---|---|---|
| When processed | On discovery (before children) | On completion (after children) |
| Parent-child order | Parent before children | Children before parent |
| In recursive DFS | Before the loop over neighbors | After the loop over neighbors |
| In iterative DFS | When popping (simple) | Requires state tracking |
| First vertex | Starting vertex | A leaf vertex |
| Last vertex | Last discovered leaf | Starting vertex |
| Mnemonic | "Arrival order" | "Departure order" |
Visual Comparison:
Tree: A
/ \
B C
/ \
D E
Pre-order: A, B, D, E, C
↓ ↓ ↓ ↓ ↓
[Discovery order]
Post-order: D, E, B, C, A
↓ ↓ ↓ ↓ ↓
[Completion order]
DFS Traversal Timeline:
Time: 1 2 3 4 5 6 7 8 9 10
|--|--|--|--|--|--|--|--|--|
A: [==================A=======]
B: ..[=========B===]..........
D: ....[==D==]................
E: ...........[==E==].........
C: ...................[==C==].
d d d f d f f f f
A B D D E E B C A
Pre: A B D E
Post: D E B C A
The discovery and finish times provide a powerful framework for classifying edges in a graph. This classification is fundamental to many graph algorithms.
The Four Edge Types:
When DFS encounters an edge (u, v) while exploring vertex u:
Tree Edge: v is unvisited. This edge becomes part of the DFS tree.
Back Edge: v is an ancestor of u (still on the stack/active).
Forward Edge: v is a descendant of u (already fully explored).
Cross Edge: v is neither ancestor nor descendant (different subtree).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
from enum import Enum class EdgeType(Enum): TREE = "Tree" # Part of DFS tree BACK = "Back" # To ancestor (indicates cycle) FORWARD = "Forward" # To descendant (directed only) CROSS = "Cross" # To different subtree (directed only) def classify_edges(graph, start_vertices): """ Classify all edges in a directed graph using DFS. Returns: Dictionary mapping each edge (u, v) to its EdgeType """ # States: 0=unvisited, 1=in-progress (on stack), 2=finished WHITE, GRAY, BLACK = 0, 1, 2 color = {v: WHITE for v in graph} discovery = {} finish = {} time = [0] edge_types = {} def dfs(u): time[0] += 1 discovery[u] = time[0] color[u] = GRAY # In-progress for v in graph.get(u, []): edge = (u, v) if color[v] == WHITE: # v unvisited -> Tree edge edge_types[edge] = EdgeType.TREE dfs(v) elif color[v] == GRAY: # v is in-progress (ancestor on stack) -> Back edge edge_types[edge] = EdgeType.BACK elif color[v] == BLACK: # v is finished if discovery[u] < discovery[v]: # u was discovered before v -> Forward edge edge_types[edge] = EdgeType.FORWARD else: # u was discovered after v -> Cross edge edge_types[edge] = EdgeType.CROSS color[u] = BLACK # Finished time[0] += 1 finish[u] = time[0] for start in start_vertices: if color[start] == WHITE: dfs(start) return edge_types, discovery, finish # Example with various edge typesdirected_graph = { 'A': ['B', 'C', 'D'], # A -> B, A -> C, A -> D 'B': ['D', 'E'], # B -> D (forward), B -> E 'C': ['F'], # C -> F 'D': [], # Leaf 'E': ['A', 'F'], # E -> A (back), E -> F (cross) 'F': [] # Leaf} edge_types, discovery, finish = classify_edges(directed_graph, ['A']) print("Edge Classification Results:")print("=" * 50)print(f"Discovery times: {discovery}")print(f"Finish times: {finish}")print()print("Edge Classifications:")for edge, etype in sorted(edge_types.items()): u, v = edge print(f" {u} -> {v}: {etype.value:8} (d[{u}]={discovery[u]}, d[{v}]={discovery[v]})") # Output:# Edge Classification Results:# ==================================================# Discovery times: {'A': 1, 'B': 2, 'D': 3, 'E': 5, 'F': 7, 'C': 11}# Finish times: {'D': 4, 'F': 8, 'E': 9, 'B': 10, 'C': 12, 'A': 13}## Edge Classifications:# A -> B: Tree (d[A]=1, d[B]=2)# A -> C: Tree (d[A]=1, d[C]=11)# A -> D: Forward (d[A]=1, d[D]=3) <- A discovered before D, D is descendant# B -> D: Tree (d[B]=2, d[D]=3)# B -> E: Tree (d[B]=2, d[E]=5)# C -> F: Cross (d[C]=11, d[F]=7) <- C discovered after F finished# E -> A: Back (d[E]=5, d[A]=1) <- A is ancestor of E (CYCLE!)# E -> F: Tree (d[E]=5, d[F]=7)A graph has a cycle if and only if DFS finds a back edge. This is the foundation of cycle detection algorithms. When we encounter a gray (in-progress) vertex, we've found a path from that vertex back to itself.
Edge Types in Undirected Graphs:
In undirected graphs, the classification simplifies:
Forward and cross edges do not exist in undirected graphs (every non-tree edge to an already-visited vertex is a back edge, because the vertex must be an ancestor—we can't reach vertices in other subtrees without going through a common ancestor first).
Pre-order and post-order orderings are the building blocks for many important graph algorithms. Let's explore the key applications with concrete implementations.
Topological Sort via Reverse Post-Order
For a Directed Acyclic Graph (DAG), topological order is an ordering where for every edge (u, v), u appears before v.
Key Insight: Reverse post-order of DFS gives a valid topological order.
Why it works: In post-order, a vertex appears after all its descendants. So in reverse post-order, it appears before all its descendants — exactly what topological order requires.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
def topological_sort_dfs(graph, all_vertices): """ Topological sort using DFS post-order. Returns vertices in topological order, or raises if cycle detected. """ WHITE, GRAY, BLACK = 0, 1, 2 color = {v: WHITE for v in all_vertices} postorder = [] def dfs(u): color[u] = GRAY for v in graph.get(u, []): if color[v] == GRAY: raise ValueError(f"Cycle detected! Back edge {u} -> {v}") if color[v] == WHITE: dfs(v) color[u] = BLACK postorder.append(u) for v in all_vertices: if color[v] == WHITE: dfs(v) # Reverse post-order = topological order return postorder[::-1] # Example: Task dependencies# A must be done before B, C# B must be done before D# C must be done before D# D must be done before Etask_graph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': []} topo_order = topological_sort_dfs(task_graph, ['A', 'B', 'C', 'D', 'E'])print(f"Task execution order: {topo_order}")# Output: Task execution order: ['A', 'C', 'B', 'D', 'E']# (or another valid order like ['A', 'B', 'C', 'D', 'E'])Pre-order and post-order are fundamental to understanding and applying DFS effectively.
What's Next:
With pre-order and post-order mastered, we'll analyze the time complexity of DFS — understanding why DFS runs in O(V + E) time and what this means for different graph representations and problem sizes.
You now understand the two fundamental orderings DFS produces. You can implement both in recursive and iterative forms, classify edges based on discovery/finish states, and apply these orderings to solve real problems like topological sorting and cycle detection. Next, we'll complete our DFS analysis with a rigorous look at time complexity.