pythonadvanced15 minutes

Fix Bug in Recursive Function to Calculate Maximum Path Sum in Binary Tree

The provided Python function aims to find the maximum path sum in a binary tree, where a path can start and end at any node. However, the current implementation contains bugs that lead to incorrect results and runtime errors. Your task is to identify and fix these bugs, ensuring the function correctly computes the maximum path sum.

Challenge prompt

A binary tree path is any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. The maximum path sum is the largest possible sum of the values of nodes on any path. Here is a buggy Python implementation of a function maxPathSum(root) that should return this maximum path sum for the binary tree rooted at root. Fix the code so it works correctly for any input binary tree.

Guidance

• Check how negative path sums are handled and whether they should be excluded.
• Ensure the recursive helper function correctly updates and returns the maximum single-side path sums.
• Remember that the global maximum path sum might include both left and right children's paths plus the current node's value.

Hints

• Pay attention to how you handle None nodes or leaf nodes to avoid attribute errors.
• Consider using a class attribute or mutable object to keep track of the global maximum path sum across recursion.
• Watch out for updating the maximum path sum before returning from recursion.

Starter code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')
    
    def max_gain(node):
        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 + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum

Expected output

For the tree: 1 / \ 2 3 The function should return 6, which corresponds to the path 2 -> 1 -> 3.

Core concepts

recursionbinary treedynamic programmingdebugging

Challenge a Friend

Send this duel to someone else and see if they can solve it.