#124HardTrees & BST

Binary Tree Maximum Path Sum

The tell: A path that may bend at a node, so the value returned upward differs from the value recorded.

How you get there

1The best path through a node is node + max(0, left) + max(0, right).
2The value returned to the parent can only use one branch: node + max(0, best child).
3Clamping negatives at zero encodes 'skip this branch entirely'.

Solution

Python

def max_path_sum(root) -> int:
    best = float("-inf")

    def gain(node) -> int:
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)      # negative branches are skipped
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return int(best)

Time: O(n)
Space: O(h)

What goes wrong

Returning node.val + left + right upward would let a parent use a path that bends twice.

Test yourself on DSA Next: Invert Binary Tree →