Foundation drill for this topic
Easy Stack + Visited
In plain English: Walk every reachable node in a graph by going as deep as possible before backtracking, using a stack.
Replacing the BFS queue with a stack switches from breadth-first to depth-first — LIFO explores deep before wide.
Prompt
Traverse a graph depth-first using an explicit stack.
Try to write it from scratch before scrolling down.
Solution
def dfs_iterative(graph, start):
visited = {start}
stack = [start] # stack = LIFO = depth first
order = []
while stack:
node = stack.pop()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)
return orderQuick recall drills to reinforce this pattern.
Iterative DFS avoids recursion limits. Same time complexity, explicit stack.
stack = [start]
visited = {start}
while stack:
node = stack.pop()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)Recursive DFS is the most natural graph traversal. Watch for stack overflow on deep graphs.
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.
stack = []
stack.append(x)
stack.pop()