Pre-Order and Post-Order… — Depth-First Search (DFS)… | OneNoughtOne

0/97

Data Structures & AlgorithmsGraph Algorithms

Depth-First Search (DFS) — Algorithm & Applications

LevelIntermediate

Duration90 mins

TopicGraph Algorithms

3 / 5

Pre-Order and Post-Order Traversal

Two Orderings, Endless Applications

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: Topological sorting relies on reverse post-order Detecting cycles uses the relationship between pre and post times Strongly connected components algorithms use post-order Expression tree evaluation uses post-order traversal Understanding when each ordering occurs—and why—transforms DFS from a simple traversal technique into a powerful analytical tool.

What You Will Learn

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.

Discovery Time and Finish Time

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: [d[u], f[u]] and [d[v], f[v]] are entirely disjoint — Neither is an ancestor of the other [d[v], f[v]] is entirely contained within [d[u], f[u]] — v is a descendant of u [d[u], f[u]] is entirely contained within [d[v], f[v]] — u is a descendant of v Think of it like matching parentheses: ((( ))) or ( ) ( ), but never ( ( ) ) ((overlapping/interleaved).

discovery_finish_times.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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 structure
tree = {
    '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 disjoint

Reading the Intervals: Looking at the output: A: [1, 12] contains all other intervals — A is the root, ancestor of all B: [2, 7] is nested inside A's interval — B is a descendant of A D: [3, 4] and E: [5, 6] are both inside B's interval, disjoint from each other — siblings C: [8, 11] and B: [2, 7] are disjoint — siblings under A Why This Matters: The parenthesis structure reveals the DFS tree: Nesting = ancestor/descendant relationship Disjoint = neither is ancestor of the other This structure is foundational for classifying edges (tree, back, forward, cross)

Pre-Order Traversal

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: Root/starting vertex is always first For any subtree, the subtree's root appears before all other vertices in that subtree Ancestors appear before descendants The order represents the "discovery sequence" of DFS exploration

preorder_traversal.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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 tree
tree = {
    '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 C

When 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

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: Leaves (vertices with no children) can appear early A vertex appears only after ALL its descendants have been processed Root/ancestor appears after all of its descendants The order represents the "completion sequence" of DFS exploration

postorder_traversal.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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 tree
tree = {
    '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 last

The Two-Stack Trick for Post-Order

The 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 vs Post-Order Comparison

Pre-order and post-order are two sides of the same DFS traversal. Understanding their relationship is key to using them effectively.

Pre-Order vs Post-Order: Complete Comparison
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

Use Pre-Order When...

•Building/copying structure top-down
•Need to process parent before children
•Recording discovery order matters
•Serializing trees
•Creating prefix expressions

Use Post-Order When...

•Computing bottom-up (subtree aggregates)
•Need to process children before parent
•Deleting/deallocating structures
•Topological sorting (reverse post-order)
•Evaluating expressions (postfix)

Edge Classification with Pre/Post Order

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. d[u] < d[v] (u discovered before v) v discovered directly from u Back Edge: v is an ancestor of u (still on the stack/active). d[v] < d[u] < f[u] < f[v] (v's interval contains u's) Critical: Back edges indicate cycles Forward Edge: v is a descendant of u (already fully explored). d[u] < d[v] < f[v] < f[u] (u's interval contains v's) Only in directed graphs Cross Edge: v is neither ancestor nor descendant (different subtree). f[v] < d[u] (v completely finished before u started) Only in directed graphs

edge_classification.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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 types
directed_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)

Back Edges = Cycles

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: Tree edges: Part of the DFS tree (as before) Back edges: Connect to ancestors (as before) 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).

Applications of Pre/Post Order

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.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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 E
task_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'])

Summary: Pre-Order and Post-Order

Pre-order and post-order are fundamental to understanding and applying DFS effectively.

Key Takeaways

•Discovery and finish times define intervals: Each vertex's interval d[v] to f[v] follows strict nesting (parenthesis property).
•Pre-order = discovery sequence: Vertices listed when first reached, parents before children.
•Post-order = completion sequence: Vertices listed when fully explored, children before parents.
•Iterative post-order requires state tracking: Use flags or the two-stack trick.
•Edge classification uses timing: White=unvisited, Gray=in-progress, Black=finished determines edge type.
•Back edges indicate cycles: This is the foundation of cycle detection.
•Reverse post-order = topological order: For DAGs, this gives valid dependency ordering.

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.

Page Complete

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.

Data Structures & AlgorithmsGraph Algorithms

Depth-First Search (DFS) — Algorithm & Applications

LevelIntermediate

Duration90 mins

TopicGraph Algorithms

3 / 5

Pre-Order and Post-Order Traversal

Two Orderings, Endless Applications

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: Topological sorting relies on reverse post-order Detecting cycles uses the relationship between pre and post times Strongly connected components algorithms use post-order Expression tree evaluation uses post-order traversal Understanding when each ordering occurs—and why—transforms DFS from a simple traversal technique into a powerful analytical tool.

What You Will Learn

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.

Discovery Time and Finish Time

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: [d[u], f[u]] and [d[v], f[v]] are entirely disjoint — Neither is an ancestor of the other [d[v], f[v]] is entirely contained within [d[u], f[u]] — v is a descendant of u [d[u], f[u]] is entirely contained within [d[v], f[v]] — u is a descendant of v Think of it like matching parentheses: ((( ))) or ( ) ( ), but never ( ( ) ) ((overlapping/interleaved).

discovery_finish_times.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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 structure
tree = {
    '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 disjoint

Reading the Intervals: Looking at the output: A: [1, 12] contains all other intervals — A is the root, ancestor of all B: [2, 7] is nested inside A's interval — B is a descendant of A D: [3, 4] and E: [5, 6] are both inside B's interval, disjoint from each other — siblings C: [8, 11] and B: [2, 7] are disjoint — siblings under A Why This Matters: The parenthesis structure reveals the DFS tree: Nesting = ancestor/descendant relationship Disjoint = neither is ancestor of the other This structure is foundational for classifying edges (tree, back, forward, cross)

Pre-Order Traversal

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: Root/starting vertex is always first For any subtree, the subtree's root appears before all other vertices in that subtree Ancestors appear before descendants The order represents the "discovery sequence" of DFS exploration

preorder_traversal.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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 tree
tree = {
    '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 C

When 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

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: Leaves (vertices with no children) can appear early A vertex appears only after ALL its descendants have been processed Root/ancestor appears after all of its descendants The order represents the "completion sequence" of DFS exploration

postorder_traversal.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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 tree
tree = {
    '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 last

The Two-Stack Trick for Post-Order

The 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 vs Post-Order Comparison

Pre-order and post-order are two sides of the same DFS traversal. Understanding their relationship is key to using them effectively.

Pre-Order vs Post-Order: Complete Comparison
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

Use Pre-Order When...

•Building/copying structure top-down
•Need to process parent before children
•Recording discovery order matters
•Serializing trees
•Creating prefix expressions

Use Post-Order When...

•Computing bottom-up (subtree aggregates)
•Need to process children before parent
•Deleting/deallocating structures
•Topological sorting (reverse post-order)
•Evaluating expressions (postfix)

Edge Classification with Pre/Post Order

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. d[u] < d[v] (u discovered before v) v discovered directly from u Back Edge: v is an ancestor of u (still on the stack/active). d[v] < d[u] < f[u] < f[v] (v's interval contains u's) Critical: Back edges indicate cycles Forward Edge: v is a descendant of u (already fully explored). d[u] < d[v] < f[v] < f[u] (u's interval contains v's) Only in directed graphs Cross Edge: v is neither ancestor nor descendant (different subtree). f[v] < d[u] (v completely finished before u started) Only in directed graphs

edge_classification.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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 types
directed_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)

Back Edges = Cycles

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: Tree edges: Part of the DFS tree (as before) Back edges: Connect to ancestors (as before) 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).

Applications of Pre/Post Order

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.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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 E
task_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'])

Summary: Pre-Order and Post-Order

Pre-order and post-order are fundamental to understanding and applying DFS effectively.

Key Takeaways

•Discovery and finish times define intervals: Each vertex's interval d[v] to f[v] follows strict nesting (parenthesis property).
•Pre-order = discovery sequence: Vertices listed when first reached, parents before children.
•Post-order = completion sequence: Vertices listed when fully explored, children before parents.
•Iterative post-order requires state tracking: Use flags or the two-stack trick.
•Edge classification uses timing: White=unvisited, Gray=in-progress, Black=finished determines edge type.
•Back edges indicate cycles: This is the foundation of cycle detection.
•Reverse post-order = topological order: For DAGs, this gives valid dependency ordering.

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.

Page Complete

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.

Pre-Order and Post-Order Traversal

Two Orderings, Endless Applications

Discovery Time and Finish Time

Pre-Order Traversal

Post-Order Traversal

Pre-Order vs Post-Order Comparison

Edge Classification with Pre/Post Order

Applications of Pre/Post Order

Summary: Pre-Order and Post-Order

There’s more to understand.

Pre-Order and Post-Order Traversal

Two Orderings, Endless Applications

Discovery Time and Finish Time

Pre-Order Traversal

Post-Order Traversal

Pre-Order vs Post-Order Comparison

Edge Classification with Pre/Post Order

Applications of Pre/Post Order

Summary: Pre-Order and Post-Order

There’s more to understand.