Micro-questions over the DFS pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.

This bank is about recognising the problem shape. The mechanics are in the DFS bank.


A. The shape

1. What shape of problem is DFS the right tool for?

Answer

Anything that asks you to explore every path or branch of a tree or graph — not just find one answer and stop.

2. Give the maze illustration.

Answer

Walk down each path until a dead end, then backtrack and try another.


B. The three recognitions

3. “Find all paths from root to leaves” — why DFS?

Answer

You need to explore every branch, so preorder-style DFS that builds up a path as it descends is a direct fit.

4. “Clone a graph” — why DFS?

Answer

You need to visit every node and edge exactly once, which is exactly what DFS with a visited map guarantees.

5. “Order tasks with dependencies” — why DFS?

Answer

DFS finishes exploring everything a node depends on before the node itself is done — so appending nodes as they finish (postorder) gives a valid ordering.


C. Backtracking inside DFS

6. In path_sum_ii, what does path.pop() do?

Answer

Undoes the choice before returning to the parent call — the backtracking step.

7. What happens without it?

Answer

The path keeps growing across sibling branches, so every recorded path contains nodes from branches you already left.

8. How does this relate to the backtracking pattern?

Answer

Here the undo is a side detail; in backtracking the “undo the choice before returning” mechanic is the main point of the algorithm.


D. Cycle detection

9. What two sets does the topological sort keep, and why?

Answer

visited — finished nodes, so you never redo work. visiting — nodes currently on the recursion path, which is what detects cycles.

10. Why does visiting catch cycles when visited cannot?

Answer

visited means “seen at some point”, including on a branch already finished. A cycle needs a node seen while still on the current path — which is precisely what visiting records.

11. Trace edges [[0,1],[1,2],[2,3]].

Answer

Visit 0 → 1 → 2 → 3; 3 has nothing left, append 3; backtrack appending 2, 1, 0. Reverse the finishing order: [0,1,2,3].


E. Trade-offs

12. When should you not use DFS?

Answer

When you need the shortest path — DFS explores deeply before broadly, so use BFS.

13. What is the recursion risk, and the fix?

Answer

Very deep graphs hit Python’s recursion limit. Use an iterative DFS with an explicit stack.

14. What is the difference between DFS and backtracking?

Answer

DFS traverses a structure that already exists; backtracking explores a space of decisions it generates, undoing each choice before trying the next. Backtracking is DFS over an implicit tree of choices.

15. Summarise the pattern in one sentence.

Answer

Reach for DFS when the question is about whole paths or about finishing dependencies — and keep a second set when you need to know you are still standing on the path.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes