Tree: Depth-First Search - Binary Tree Maximum Path Sum
Given the following recursive postorder code snippet for maximum path sum, what is the returned maximum path sum for the tree: root=1, left=2, right=3?
Given the following recursive postorder code snippet for maximum path sum, what is the returned maximum path sum for the tree: root=1, left=2, right=3?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace max_gain for left child (2)
Left and right children are None, so left_gain=0, right_gain=0; price_newpath=2+0+0=2; max_sum=2; return 2.Step 2: Trace max_gain for right child (3) and root (1)
Right child: price_newpath=3; max_sum=3; return 3. Root: left_gain=2, right_gain=3; price_newpath=1+2+3=6; max_sum=6; return 1+max(2,3)=4.Final Answer:
Option B -> Option BQuick Check:
Max path sum is 2+1+3=6 [OK]
Quick Trick: Sum left+root+right for max path [OK]
Common Mistakes:
MISTAKES- Returning sum of only one subtree
- Ignoring max_sum update
- Confusing return value with max_sum
Trap Explanation:
PITFALL- Candidates often confuse return value (max gain to parent) with global max path sum, leading to wrong answers.
Interviewer Note:
CONTEXT- Tests ability to mentally execute recursive DFS with global max tracking.
Master "Binary Tree Maximum 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