Tree: Depth-First Search - Path Sum
Given the following partial DFS call stack state during Path Sum execution: current node value=7, accumulated sum=10, targetSum=17, and the function returns True. Which path led to this result?
Given the following partial DFS call stack state during Path Sum execution: current node value=7, accumulated sum=10, targetSum=17, and the function returns True. Which path led to this result?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand accumulated sum meaning
Accumulated sum before current node is 10.Step 2: Add current node value to accumulated sum
10 + 7 = 17 equals targetSum, so path sum matches target.Step 3: Confirm function returns True
Indicates a root-to-leaf path with sum 17 exists including current node.Final Answer:
Option A -> Option AQuick Check:
Accumulated + current = targetSum -> True [OK]
Quick Trick: Sum includes current node to reach target [OK]
Common Mistakes:
MISTAKES- Ignoring current node value
- Confusing accumulated sum with total sum
Trap Explanation:
PITFALL- Candidates may think accumulated sum alone equals target, ignoring current node.
Interviewer Note:
CONTEXT- Tests ability to reason backward through DFS state.
Master "Path Sum" 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