Find the Maximum Sum Path in a Binary Tree

Given a binary tree, this problem requires finding the maximum sum path from the root to a leaf. For example, in the tree shown above, the maximum sum path would be 3 + 5 + 10 + 2 + 11 = 31. This can be done using recursion.

Problem

Given a binary tree, find the maximum sum path from root to leaf.
For example, given the following tree:
root = [10,5,-3,3,2,null,11,3,-2,null,1],
10
/ \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1
Return 3 + 5 + 10 + 2 + 11 = 31.

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.
by kayakane
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
        self.max_gain(root)
        return self.max_sum
    
    def max_gain(self, node):
        if not node:
            return 0
        
        left_gain = max(self.max_gain(node.left), 0)
        right_gain = max(self.max_gain(node.right), 0)
        
        price_newpath = node.val + left_gain + right_gain
        
        self.max_sum = max(self.max_sum, price_newpath)
        
        return node.val + max(left_gain, right_gain)

A.I. Evaluation of the Solution

The candidate's solution correctly solves the problem. The approach is to recursively find the maximum sum path from each node to its leaves, and then compare the paths to find the overall maximum sum path.

Evaluated at: 2022-12-12 02:15:38