Tree: Depth-First Search - Path Sum
Given the following optimal DFS code for Path Sum, what is the return value for the tree with root=5, left=4, right=8, left.left=11, targetSum=20?
Given the following optimal DFS code for Path Sum, what is the return value for the tree with root=5, left=4, right=8, left.left=11, targetSum=20?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace dfs on left path 5->4->11
Sum = 5 + 4 + 11 = 20, matches targetSum.Step 2: Return True at leaf node where sum equals target
DFS returns True, so overall function returns True.Final Answer:
Option D -> Option DQuick Check:
Path sum found -> True [OK]
Quick Trick: Sum along root-to-leaf path equals target -> True [OK]
Common Mistakes:
MISTAKES- Stopping at non-leaf nodes
- Miscomputing sum accumulation
Trap Explanation:
PITFALL- Candidates may forget to check leaf node condition and return prematurely.
Interviewer Note:
CONTEXT- Tests ability to mentally execute DFS with sum accumulation.
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