[Solved] Examine the following recursive code snippet for maximum path sum.... Which line contains the subtle bug that causes incorrect results on trees with negative values? | Tree: Depth-First Search

Tree: Depth-First Search - Binary Tree Maximum Path Sum

Examine the following recursive code snippet for maximum path sum. Which line contains the subtle bug that causes incorrect results on trees with negative values? ```python def max_gain(node): nonlocal max_sum if not node: return 0 left_gain = max_gain(node.left) right_gain = max_gain(node.right) price_newpath = node.val + left_gain + right_gain max_sum = max(max_sum, price_newpath) return node.val + left_gain + right_gain ```

ALine returning node.val + left_gain + right_gain instead of node.val + max(left_gain, right_gain)

BLine updating max_sum with price_newpath instead of node.val only

CLine returning 0 for null nodes

DLine computing price_newpath as sum of node and gains

Step-by-Step Solution

Solution:

Step 1: Understand return value role
Return value must represent max gain from current node to parent along one path (not both subtrees).
Step 2: Identify bug
Returning sum of both left and right gains causes incorrect double counting and invalid path sums.
Final Answer:
Option A -> Option A
Quick Check:
Return should be node.val + max(left_gain, right_gain) [OK]

Quick Trick: Return max gain from one subtree, not sum of both [OK]

Common Mistakes:

MISTAKES

Returning sum of both subtrees to parent
Ignoring negative gains
Updating max_sum incorrectly

Trap Explanation:

PITFALL

Candidates often return sum of both subtree gains, which breaks the path definition and leads to wrong max sums.

Interviewer Note:

CONTEXT

Tests ability to spot subtle recursion return value bugs.

Master "Binary Tree Maximum Path Sum" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

Which line contains the subtle bug that causes incorrect results on trees with negative values?

Step 1: Understand return value role

Step 2: Identify bug

Final Answer:

Quick Check:

Want More Practice?