Tree: Depth-First Search - Binary Tree Maximum Path Sum
Using the same recursive code, what is the maximum path sum returned for a single-node tree with value -5?
Using the same recursive code, what is the maximum path sum returned for a single-node tree with value -5?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace max_gain for single node (-5)
Left and right children are None, so left_gain=0, right_gain=0; price_newpath=-5+0+0=-5; max_sum=-5; return -5+max(0,0)=-5.Step 2: Return max_sum
max_sum is -5, which is the correct maximum path sum for this single-node tree.Final Answer:
Option A -> Option AQuick Check:
Negative node value is correctly handled [OK]
Quick Trick: Max path sum can be negative if all nodes negative [OK]
Common Mistakes:
MISTAKES- Returning 0 for negative single node
- Ignoring negative values in max_sum
- Assuming path sum must be non-negative
Trap Explanation:
PITFALL- Candidates often return 0 for empty or negative nodes, missing that max path sum can be negative.
Interviewer Note:
CONTEXT- Tests handling of edge cases with negative values and single nodes.
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