Depth-First Search (DFS)
Explore as far as possible down one path before backtracking — trees, graphs, and backtracking
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
explores a tree or graph by going as deep as possible down one path before backtracking — the opposite of exploring level by level.
Recursive DFS on a tree:
python def dfs(node, visited=None): if node is None: return print(node.val) # "visit" the node for neighbor in node.children: dfs(neighbor)
On a graph, you must track visited nodes — graphs can have cycles a tree never has:
python def dfs_graph(graph, start, visited=None): if visited is None: visited = set() visited.add(start) # mark BEFORE recursing — prevents infinite loops for neighbor in graph[start]: if neighbor not in visited: dfs_graph(graph, neighbor, visited) return visited
The iterative version uses an explicit stack instead of the call stack:
python def dfs_iterative(graph, start): visited = {start} stack = [start] while stack: node = stack.pop() # LIFO — most recently added explored next for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor) return visited
Backtracking is DFS with undo. Generating permutations, combinations, or solving mazes/Sudoku is DFS where each recursive call tries a choice, recurses, then *undoes* the choice on the way back up: ``python def permutations(nums): result = [] def backtrack(path, remaining): if not remaining: result.append(path[:]) # found a full permutation return for i, n in enumerate(remaining): path.append(n) # choose backtrack(path, remaining[:i] + remaining[i+1:]) # explore path.pop() # un-choose (backtrack) backtrack([], nums) return result
When to reach for DFS: "does a path exist," "find all paths/combinations," tree traversals, connected components, cycle detection, anything where you need to fully explore one branch before trying the next.
Examples
Counting connected components in a graph
Every unvisited node starts a fresh DFS — each call explores exactly one connected component
def count_components(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
components = 0
for node in range(n):
if node not in visited:
dfs(node) # explore the whole component
components += 1
return components
print(count_components(5, [(0, 1), (1, 2), (3, 4)])) # 2 componentsDetecting a cycle in a directed graph
Three-color DFS — a GRAY node revisited mid-recursion means a back edge, which means a cycle
def has_cycle(graph, n):
WHITE, GRAY, BLACK = 0, 1, 2 # unvisited, in-progress, done
color = [WHITE] * n
def dfs(node):
color[node] = GRAY # currently on the call stack
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # back edge — found a cycle
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK # fully explored, safe
return False
return any(color[i] == WHITE and dfs(i) for i in range(n))How well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Breadth-First Search (BFS)