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

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

Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?

def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum

ALine returning 0 for null node

BLine computing current_path_sum = node.val + left_gain + right_gain

CLine updating max_sum = max(max_sum, current_path_sum)

DLine returning node.val + left_gain + right_gain

Step-by-Step Solution

Solution:

Step 1: Understand return value meaning
The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).
Step 2: Identify the bug
Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.
Final Answer:
Option D -> Option D
Quick Check:
Return should be node.val + max(left_gain, right_gain) [OK]

Quick Trick: Return value must be single path gain, not sum of both children [OK]

Common Mistakes:

MISTAKES

Returning sum of both children gains
Ignoring negative gains
Updating max_sum incorrectly

Trap Explanation:

PITFALL

Returning sum of both children looks correct for max path sum but breaks recursion gain logic.

Interviewer Note:

CONTEXT

Tests if candidate understands difference between max path sum and max gain returned to parent.

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

Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?

Step 1: Understand return value meaning

Step 2: Identify the bug

Final Answer:

Quick Check:

Want More Practice?