Binary Tree Maximum Path Sum

def maxPathSum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))    # drop < 0
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)  # bend
        return node.val + max(left, right)  # one arm
    gain(root)
    return best

Binary Tree Maximum Path Sum. A path is any chain of connected nodes, each used at most once, and it doesn't have to pass through the root. Find the largest path sum.

Here's the example. Minus ten is the root, with nine on the left and twenty on the right. Twenty's children are fifteen and seven. The best path is fifteen, twenty, seven: forty-two. It skips the root.

The naive way tries every pair of endpoints. That's about n squared paths, too slow for a big tree.

The key idea: every path bends at one highest node, and reaches down at most two arms. So ask each node: what's the best gain down just one arm? Work up from the leaves. If an arm's gain is negative, drop it and take zero.

In code, a helper returns a node's one-arm gain. It takes the left and right gains, floored at zero. It updates the best with the node plus both arms: the path that bends here. Then it returns the node plus the bigger arm, since a parent can extend only one side.

Let's run it. Nine is a leaf: gain nine, best nine. Fifteen raises the best to fifteen. Seven gives seven. At twenty, bending gives fifteen plus twenty plus seven: forty-two, the new best. Twenty sends up twenty plus fifteen: thirty-five. At the root, bending gives minus ten plus nine plus thirty-five: only thirty-four. The best stays forty-two.

Each node is visited once, so the time is O of n. The space is the recursion depth, the tree's height.

Gains flow up, the best bend wins. That's Binary Tree Maximum Path Sum.