Introduction

Depth-first search, or DFS, is a traversal algorithm for graphs and trees that explores one path as deeply as possible before backtracking. It is a foundational technique because many larger algorithms, including cycle detection and topological sorting, are built directly on top of it.

How DFS Traversal Works

DFS starts from a chosen node, marks it as visited, then recursively or iteratively visits an unvisited neighbor. When it reaches a node with no more unvisited neighbors, it backtracks to the previous node and continues from there.

That “go deep first, then come back” behavior is the defining feature.

Consider this graph as an adjacency list:

1graph = {
2    "A": ["B", "C"],
3    "B": ["D", "E"],
4    "C": ["F"],
5    "D": [],
6    "E": [],
7    "F": []
8}

If we start at A, one possible DFS order is:

A, B, D, E, C, F

The exact order can vary based on neighbor ordering, but the algorithmic pattern stays the same.

Recursive DFS

The recursive form is often the easiest to understand because the call stack naturally handles backtracking.

1graph = {
2    "A": ["B", "C"],
3    "B": ["D", "E"],
4    "C": ["F"],
5    "D": [],
6    "E": [],
7    "F": []
8}
9
10visited = set()
11
12def dfs(node):
13    if node in visited:
14        return
15
16    visited.add(node)
17    print(node)
18
19    for neighbor in graph[node]:
20        dfs(neighbor)
21
22dfs("A")

This visits a node, processes it, then recursively traverses each neighbor.

For trees, recursion is especially natural because there is usually a single path from the root to each node. For graphs, the visited set is essential. Without it, cycles can cause infinite recursion.

Iterative DFS with an Explicit Stack

The iterative form uses your own stack instead of the language call stack. It is useful when recursion depth could become a problem.

1graph = {
2    "A": ["B", "C"],
3    "B": ["D", "E"],
4    "C": ["F"],
5    "D": [],
6    "E": [],
7    "F": []
8}
9
10def dfs_iterative(start):
11    visited = set()
12    stack = [start]
13
14    while stack:
15        node = stack.pop()
16        if node in visited:
17            continue
18
19        visited.add(node)
20        print(node)
21
22        for neighbor in reversed(graph[node]):
23            stack.append(neighbor)
24
25dfs_iterative("A")

The reversed call keeps the traversal order similar to the recursive version when using a list-based stack.

DFS on Trees Versus Graphs

Trees are a special case of graphs with no cycles. That means DFS on a tree can sometimes skip the visited set because each child is reached through a single parent.

Graphs are different. A graph may contain:

• cycles
• cross edges
• disconnected components

For a general graph traversal, always assume you need visited.

If the graph is disconnected, one DFS call from a single start node does not reach every vertex. In that case, loop over all nodes and start DFS again for any node that has not been visited yet.

1def full_dfs(graph):
2    visited = set()
3
4    def walk(node):
5        if node in visited:
6            return
7        visited.add(node)
8        print(node)
9        for neighbor in graph[node]:
10            walk(neighbor)
11
12    for node in graph:
13        walk(node)

Common Uses of DFS

DFS is not only for printing traversal order. It is useful for:

• finding connected components
• detecting cycles
• topological sorting in directed acyclic graphs
• solving mazes and backtracking problems
• checking reachability between nodes

Many interview questions that appear different on the surface reduce to “do a DFS and track a little more state.”

Time and Space Complexity

For a graph represented with adjacency lists, DFS runs in O(V + E) time, where V is the number of vertices and E is the number of edges. Each node is visited once, and each edge is examined at most a constant number of times.

Space complexity is O(V) because of the visited set and either the recursion stack or the explicit stack.

Common Pitfalls

The most common mistake is forgetting the visited check in graphs with cycles. That can lead to infinite recursion or repeated work.

Another issue is assuming DFS finds the shortest path in an unweighted graph. It does not. Breadth-first search is the right default for shortest path length in that case.

Recursion depth is another practical concern. On large or deeply nested graphs, iterative DFS can be safer than recursive DFS in languages with limited recursion depth.

Summary

• DFS explores one branch deeply before backtracking.
• It can be implemented recursively or with an explicit stack.
• Use a visited set for general graphs to avoid cycles and repeated work.
• DFS is a building block for cycle detection, components, and many backtracking problems.
• Its typical complexity is O(V + E) with adjacency-list graphs.