The Concept
The concept
DFS vs BFS: The Fundamental Choice
Every tree/graph problem starts with one decision: depth-first or breadth-first? The choice is not about preference — it's about what you're looking for:
DFS (depth-first search) goes deep before going wide. It explores one path all the way to a leaf before backtracking. Use DFS when you need to: find any path (not necessarily shortest), examine the full structure of a subtree, enumerate all possible solutions (with backtracking), or compute something over a path (max depth, path sum). DFS uses a stack (or recursion, which is an implicit stack) and uses O(h) space where h is the height.
BFS (breadth-first search) goes wide before going deep. It explores all nodes at distance 1, then distance 2, then distance 3. Use BFS when you need to: find the shortest path in an unweighted graph (BFS guarantees the first time you reach a node is via the shortest path), process nodes level by level, or find the nearest node satisfying a condition. BFS uses a queue and uses O(w) space where w is the maximum width of the tree.
The critical insight: BFS finds shortest paths; DFS finds paths. If the problem says "shortest," "nearest," "minimum steps," or "fewest edges" in an unweighted graph — BFS. If the problem says "all paths," "does a path exist," "maximum depth," or involves backtracking — DFS.
The patterns
DFS — depth-first search
Use when: path existence, max/min over a path, structure of a subtree, all solutions (with backtracking).
You need to find the shortest path from node A to node B in an unweighted graph. Should you use BFS or DFS, and why?
BFS explores all nodes at distance 1, then distance 2, etc. The first time BFS reaches node B, it's guaranteed to be via the shortest path (fewest edges). DFS might find a path, but not necessarily the shortest — it could go deep into a long path before finding a shorter one. For shortest path in unweighted graphs, BFS is the correct choice.
# Recursive DFS on a binary tree
def max_depth(root) -> int:
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# O(n) time, O(h) space (h = height; O(log n) balanced, O(n) skewed)
# Iterative DFS on a graph (with visited set)
def dfs(graph: dict, start: str) -> list[str]:
visited, stack, order = set(), [start], []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
stack.extend(graph[node]) # push neighbours
return order
BFS — breadth-first search
Use when: shortest path in unweighted graph, level-order traversal, "minimum steps/hops."
from collections import deque
def bfs_shortest(graph: dict, start: str, target: str) -> int:
visited = {start}
queue = deque([(start, 0)]) # (node, distance)
while queue:
node, dist = queue.popleft()
if node == target:
return dist
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append((nbr, dist + 1))
return -1
# O(V + E) — BFS guarantees the FIRST time you reach a node is the shortest path
Try it yourself — run BFS over a small graph and see the shortest hop-count come out, then edit the graph to add or remove edges:
from collections import deque
def bfs_shortest(graph: dict, start: str, target: str) -> int:
visited = {start}
queue = deque([(start, 0)])
while queue:
node, dist = queue.popleft()
if node == target:
return dist
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append((nbr, dist + 1))
return -1
# Try it: edit this adjacency list and see how the shortest path changes
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C", "E"],
"E": ["D"],
}
for target in ["A", "B", "D", "E"]:
hops = bfs_shortest(graph, "A", target)
print(f"A -> {target}: {hops} hop(s)")
DFS vs BFS — the decision rule
DFS : path existence · max/min over subtree · all permutations/combinations
BFS : shortest path (unweighted) · level-by-level processing · "minimum steps"
Either: connected components · cycle detection · reachability
The key tell: "shortest/minimum" in an unweighted graph → BFS.
Backtracking — DFS that undoes choices
Use when: generate all combinations, permutations, subsets, or valid arrangements.
def subsets(nums: list[int]) -> list[list[int]]:
result: list[list[int]] = []
def backtrack(start: int, current: list[int]) -> None:
result.append(list(current)) # snapshot before expanding
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1, current) # explore
current.pop() # UNDO — the backtrack step
backtrack(0, [])
return result
The template is always: choose → explore → undo. Without the undo, choices bleed into sibling branches.
Topological Sort (Kahn's algorithm) — for DAGs / dependencies
from collections import deque
def topo_sort(n: int, prereqs: list[list[int]]) -> list[int]:
graph = [[] for _ in range(n)]
in_degree = [0] * n
for course, pre in prereqs:
graph[pre].append(course)
in_degree[course] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nbr in graph[node]:
in_degree[nbr] -= 1
if in_degree[nbr] == 0:
queue.append(nbr)
return order if len(order) == n else [] # empty -> cycle exists
# Directly models ML pipeline DAGs, dependency resolution, and build systems
Worked Example: Number of Islands (BFS/DFS)
from collections import deque
def num_islands(grid: list[list[str]]) -> int:
"""Count connected '1' regions in a 2D grid."""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
count = 0
def bfs(r: int, c: int) -> None:
queue = deque([(r, c)])
visited.add((r, c))
while queue:
cr, cc = queue.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = cr + dr, cc + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == '1' and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r, c) not in visited:
bfs(r, c)
count += 1
return count
# Time: O(rows × cols) — each cell visited once
# Space: O(rows × cols) — visited set + queue
# Interview tip: say "BFS because we need to flood-fill connected regions"
# Alternative: DFS with stack — same complexity, but BFS avoids recursion limit
Cycle Detection in Directed Graph (Color Marking)
def has_cycle(graph: dict[int, list[int]], n: int) -> bool:
"""Detect cycle using white/grey/black coloring."""
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(node: int) -> bool:
if color[node] == GREY: # back edge → cycle
return True
if color[node] == BLACK: # already processed
return False
color[node] = GREY
for nbr in graph.get(node, []):
if dfs(nbr):
return True
color[node] = BLACK
return False
return any(dfs(i) for i in range(n) if color[i] == WHITE)
# WHITE = unvisited, GREY = in current DFS path, BLACK = fully processed
# If we reach a GREY node during DFS → back edge → cycle exists
Union-Find (Disjoint Set Union)
class UnionFind:
"""Near-O(1) connected components and cycle detection."""
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
px, py = self.find(x), self.find(y)
if px == py:
return False # already connected → would create a cycle
# Union by rank: attach shorter tree under taller
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
# Usage: detect cycle in undirected graph
# uf = UnionFind(n)
# for u, v in edges:
# if not uf.union(u, v):
# print("Cycle detected!")
# Time: O(α(n)) per operation — inverse Ackermann, practically constant
Binary search trees
A binary search tree keeps one invariant at every node: everything in the left subtree is less than or equal to the node, everything in the right subtree is greater. (Where equal values go is a convention; this lab sends them left.) Two consequences do all the work:
- Insert by walking down. Compare with the current node and go left or right until you reach an empty slot. That is O(h) for a tree of height h.
- In-order traversal is sorted. Visit left subtree, node, right subtree, and the values come out in order. That is how a BST sorts.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data, self.left, self.right = data, left, right
def insert(root, value):
if root is None:
return TreeNode(value)
if value <= root.data: # equal values go left
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(node):
if node is None:
return []
return in_order(node.left) + [node.data] + in_order(node.right)
root = None
for v in [4, 2, 6, 1, 3, 5, 7]:
root = insert(root, v)
print(in_order(root)) # [1, 2, 3, 4, 5, 6, 7]
The height is the catch. Insert values that are already sorted and every node goes right: the "tree" is a linked list, h = n, and every operation is O(n). Balanced variants (AVL, red-black) rotate on insert to keep h at O(log n); in an interview, saying so is usually enough.
Interview discipline
State your traversal before coding:
"This is BFS because we need the minimum number of hops — BFS guarantees shortest path in an unweighted graph."
Common edge cases to mention: null/empty root, disconnected graph (loop over all nodes), cycle detection (track visited).