Tree: Depth-First Search - Path Sum II (All Root-to-Leaf Paths)
Given the following iterative DFS code for Path Sum II, what is the output for the tree with root=1, left=2, right=3 and targetSum=3?
Given the following iterative DFS code for Path Sum II, what is the output for the tree with root=1, left=2, right=3 and targetSum=3?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace stack operations
Start with stack=[(1,[1],1)]. Pop (1,[1],1), push right (3,[1,3],4), left (2,[1,2],3).Step 2: Check leaf nodes and sums
Pop (2,[1,2],3), leaf node with sum=3 equals target, add [1,2] to result.Final Answer:
Option B → Option BQuick Check:
Only path [1,2] sums to 3 [OK]
Quick Trick: Trace stack pushes and pops carefully [OK]
Common Mistakes:
MISTAKES- Confusing order of pushing left/right
- Mixing node values in path
Trap Explanation:
PITFALL- Candidates often confuse path order or sum calculation leading to wrong path selection.
Interviewer Note:
CONTEXT- Tests ability to mentally execute iterative DFS with path tracking.
Master "Path Sum II (All Root-to-Leaf Paths)" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes