Binary Tree Maximum Path Sum

Description

Find the largest sum on any nonempty simple path in a nonempty tree; the path need not pass through the root.

Solution

import sys

sys.setrecursionlimit(100_000)

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node:
            return 0
        left, right = max(0, gain(node.left)), max(0, gain(node.right))
        best = max(best, node.val+left+right)
        return node.val + max(left, right)
    gain(root)
    return best

Examples

Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.

Approach

Each call returns its best one-branch gain, while a global best can combine both branches through that node.