DFS templates and traversal state
Why you care
Dependency trees, org charts, folder walks and lineage graphs all arrive as "node plus its neighbours". The job bug is state: a missing visited set that loops for ever on one cyclic row, or a recursive walk that dies on the one deep chain in production. Interviewers ask for DFS because every mistake is visible. This card owns the template later cards reuse.
Explain like I'm 5
You explore a cave with a ball of thread and a piece of chalk. At each junction you take the first unmarked tunnel until a dead end, then follow the thread back to the last junction with an unexplored tunnel. Chalk means "been here". The thread is the stack. Forget the chalk and a loop in the cave walks you in circles.
Core concept
The rule: mark a node when you enter it, finish its neighbours, then mark it done.
- Entry work (record preorder, mark in progress) happens before the neighbour loop; exit work (record postorder, mark done) after it.
- A general graph needs a visited set. A rooted tree with downward edges does not. An undirected tree stored with edges both ways needs a parent skip instead.
- Disconnected input needs an outer loop over every node.
- Recursion costs one Python frame per level. The default recursion limit is 1000 (check
sys.getrecursionlimit()). An explicit stack of(node, iterator)pairs removes it. - Adjacency list cost: O(V + E) time; the visited set is O(V) and the stack up to O(V). On a tree, recursion uses O(height).
Use DFS for entry/exit order, cycle detection and "everything below this node". Use BFS (BFS, level-order and grid traversal) for fewest edges; a DFS path is valid, not shortest.
Minimal example Visited makes a cycle and an island safe
graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"], "e": []}
order, seen = [], set()
def dfs(n):
seen.add(n); order.append(n)
for m in graph[n]:
if m not in seen:
dfs(m)
for n in graph:
if n not in seen:
dfs(n)
print(order, len(seen))['a', 'b', 'd', 'c', 'e'] 5In production Iterative DFS with entry, exit and back edges
Pinterest-style category data has missing parents and the odd loop. This version uses three states (absent, 1 = in progress, 2 = done) and an explicit stack.
import sys
def dfs_all(graph):
color, pre, post, back = {}, [], [], []
for root in graph:
if root in color:
continue
color[root] = 1; pre.append(root)
stack = [(root, iter(graph.get(root, ())))]
while stack:
node, it = stack[-1]
for nxt in it:
state = color.get(nxt)
if state is None:
color[nxt] = 1; pre.append(nxt)
stack.append((nxt, iter(graph.get(nxt, ()))))
break
if state == 1:
back.append((node, nxt)) # edge into an ancestor: a cycle
else:
color[node] = 2; post.append(node); stack.pop()
return pre, post, back
def recursive_visit(graph, n, seen):
seen.add(n)
for m in graph.get(n, ()):
if m not in seen:
recursive_visit(graph, m, seen)
g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"], "e": ["e"], "f": ["ghost"]}
print(dfs_all(g))
print(dfs_all({}))
print(dfs_all({"x": []}))
chain = {i: [i + 1] for i in range(5000)}
pre, post, back = dfs_all(chain)
print(len(pre), len(post), back, sys.getrecursionlimit())
try:
recursive_visit(chain, 0, set())
except RecursionError:
print("RecursionError on a 5000-deep chain")(['a', 'b', 'd', 'c', 'e', 'f', 'ghost'], ['d', 'b', 'c', 'a', 'e', 'ghost', 'f'], [('d', 'a'), ('e', 'e')])
([], [], [])
(['x'], ['x'], [])
5001 5001 [] 1000
RecursionError on a 5000-deep chainSee it happen One walk, one back edge, one new component
- Enter a: it is marked in progress before any neighbour is looked at.
- Follow a to b, then b to d; all three are now in progress and sit on the stack.
- d looks at a, finds it still in progress, and records a back edge: that is the cycle.
- d and then b exit and are marked done; the stack unwinds to a.
- a takes its second edge to c; c finds d already done, so it does not walk into d again.
- The outer loop reaches e, which nothing points to, and starts a second walk there.
In your world
The situation
Your Jenkins job rebuilds a lineage table from a parent_id column in Postgres. Each row is walked upward with a recursive helper.
What actually breaks
One bad load writes a row whose parent is its own grandchild. The helper never ends; Jenkins times out after 60 minutes with 0 rows written. On another night a chain is 1,400 deep and the job dies with RecursionError, though every 6-level test passed.
What you'd do on Monday
Walk with an explicit stack and treat a back edge as bad data to report.
parents = {row["id"]: row["parent_id"] for row in extract}
children = {}
for child, parent in parents.items():
children.setdefault(parent, []).append(child)
pre, post, cycles = dfs_all(children) # template from the production block
if cycles:
raise SystemExit(f"{len(cycles)} cyclic edges, first: {cycles[0]}")Imagine you work at Pinterest
The numbers
Illustrative: 2,000,000 nodes, 5,000,000 edges, one chain 50,000 deep. A set of 2M ints measured 67 MB for the table alone (sys.getsizeof), before the int objects; a bytearray(2_000_000) of state flags is 2 MB. Time is V + E = 7M steps, seconds in Python.
What the Scenario-A answer does here
The Scenario A fix still works: explicit stack, same output. It gets heavy because each worker holds a set per walk.
What flips at this scale
Number the nodes 0..V-1 once and keep state in a bytearray (0 new, 1 in progress, 2 done): 67 MB becomes 2 MB, over 30x less, and components can be split across workers. The state representation changes, not the algorithm.
The trade-off you'd defend
I would defend dense integer ids and a flag array over a set of string ids, trading a one-off id-mapping pass for a visited structure over 30x smaller.
Illustrative figures to show the arithmetic; not Pinterest-published. The 67 MB is a local sys.getsizeof of a 2M-int set on CPython 3.11.
Gotchas
Cycle makes the walk run for ever
The job never finishes; with a counter it hits the cap you set.
No visited set, or marking after the neighbour loop, on a graph with a cycle.
Mark on entry. The demo stops itself after 100 calls.
g = {"a": ["b"], "b": ["a"]}
calls = 0
def walk(n):
global calls
calls += 1
if calls > 100:
raise RuntimeError("cap hit: cycle with no visited set")
for m in g[n]:
walk(m)
try:
walk("a")
except RuntimeError as e:
print(calls, e)101 cap hit: cycle with no visited setUndirected tree reports a cycle that is not there
A clean tree is rejected as cyclic.
Each edge is stored twice, so every child sees its parent as in progress.
Pass the parent down and ignore exactly that neighbour.
tree = {"r": ["x", "y"], "x": ["r"], "y": ["r"]}
def has_cycle(n, parent, state):
state[n] = 1
for m in tree[n]:
if m == parent:
continue
if state.get(m) == 1 or (m not in state and has_cycle(m, n, state)):
return True
return False
def naive(n, state):
state[n] = 1
return any(state.get(m) == 1 or (m not in state and naive(m, state)) for m in tree[n])
print("no parent check:", naive("r", {}), "| parent check:", has_cycle("r", None, {}))no parent check: True | parent check: FalseRecursive walk dies on one deep chain
RecursionError on production data only, shown in the production block.
One frame per level against a default limit of 1000.
Explicit stack. Raising sys.setrecursionlimit can crash the interpreter instead.
Tricky questions
Yes, it reached b, so it is a valid shortest path.
It is a path, not the one with fewest edges: with a-b and a-c-b, DFS may take the long way. Use BFS for hop counts.
Scenario question
You're handed a Postgres table of 3 million (id, parent_id) rows and asked for every node's depth and subtree size, rejecting bad data.
Model answer
I'd build a children map and run an iterative DFS with three states, taking depth at entry and subtree size at exit; a back edge is bad data. It is O(V + E) with O(V) state. The trade-off is RAM: when the map no longer fits in memory I would use a recursive CTE.
Interview corner
CommonWrite DFS for a graph. What state does it need?
TrickHow do you detect a cycle in a directed graph with DFS?
Experience checkHave you hit a recursion limit in real code?
Memory hook
A cave, chalk and a thread: chalk on entry, thread back on exit.
Mark on entry, finish on exit, loop over every node, and use an explicit stack when depth is unbounded.
Self-check
Which edge shows a cycle in a directed DFS?
An edge to a node that is still in progress.
Why does a disconnected graph need an outer loop?
One walk only reaches its own component.
Time and extra space of DFS on an adjacency list?
O(V + E) time; O(V) for visited and up to O(V) for the stack.
Time dfs_all on chains of 5,000, 20,000 and 100,000 nodes. Paste the three timings and the line where the recursive version raises RecursionError at 5,000.