Bird
Raised Fist0

Given the following graph represented as adjacency list: [[1,2],[3],[3],[]], what is the output of the iterative DFS allPathsSourceTarget function?

easy🧾 Code Trace Q3 of Q15
Topological Sort - All Paths From Source to Target (DAG)
Given the following graph represented as adjacency list: [[1,2],[3],[3],[]], what is the output of the iterative DFS allPathsSourceTarget function?
A[[0,1,3],[0,2,3]]
B[[0,1],[0,2]]
C[[0,3]]
D[[1,3],[2,3]]
Step-by-Step Solution
Solution:
  1. Step 1: Trace stack operations

    Start with stack [(0,[0])]. Pop (0,[0]), neighbors 1 and 2 pushed: stack [(1,[0,1]), (2,[0,2])].
  2. Step 2: Continue until target reached

    Pop (2,[0,2]), neighbor 3 pushed: stack [(1,[0,1]), (3,[0,2,3])]. Pop (3,[0,2,3]) -> target reached, add path. Pop (1,[0,1]), neighbor 3 pushed: stack [(3,[0,1,3])]. Pop (3,[0,1,3]) -> target reached, add path.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Paths [[0,1,3],[0,2,3]] match expected output [OK]
Quick Trick: Stack DFS builds paths ending at target [OK]
Common Mistakes:
MISTAKES
  • Confusing node labels with path contents
  • Forgetting to append full path when target reached
Trap Explanation:
PITFALL
  • Candidates often forget to append the full path or confuse partial paths with final results.
Interviewer Note:
CONTEXT
  • Tests candidate's ability to mentally execute iterative DFS with path tracking.
Master "All Paths From Source to Target (DAG)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes