Binary Tree Maximum Path Sum

A path that may bend at its highest point rather than run root to leaf, combined with values that can be negative. The moment the best answer at a node is not the value you can pass to its parent, you are in this pattern.

For every node, compute the longest downward path from it into each subtree, then combine to get the best path bending at that node. Repeat for all nodes and take the maximum.

O(n squared), because computing the downward best at every node re-walks its whole subtree.

The recomputation is the problem, and it is the standard signal to fold the work into a single post-order pass. Every node already learns its childrens best downward value while the recursion returns, so computing it again from scratch is pure waste. The fix is not a new idea, it is doing the same arithmetic on the way back up.

The difficulty in this problem is that two different quantities live at every node and beginners conflate them. Separating them is the whole solution.

The first is the best path that bends at this node. It may descend into the left subtree, come up through this node, and descend into the right. That is a candidate for the global answer, and it is the number you record.

The second is the best path that passes through this node on its way to the parent. A path going through the parent enters this node once and leaves once, so it can use at most one child. That is the number you return. Returning the bent value instead is the classic bug, because it lets the parent build a path that visits this node twice, which is not a path.

Clamping each child at zero expresses the last piece: a subtree whose best contribution is negative is worth skipping entirely, and taking the maximum with zero says exactly that without a branch. The clamp applies only to what children contribute, never to the node itself, because every path contains at least one node.

def maxPathSum(root):
    best = float('-inf')          # not 0: an all-negative tree has a negative answer

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)      # a negative branch is worth skipping
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)   # bends here: record only
        return node.val + max(left, right)          # straight: safe to pass up

    gain(root)
    return best

Seed the running best at negative infinity rather than zero. A tree consisting of a single node holding -3 has answer -3, and a zero seed would report 0, which is not a path at all.

The clamp is on the child gains, and the node value is added unclamped. If you clamp the node value too, an all-negative tree returns zero for the same wrong reason.

One pass, constant work per node, so linear time and stack-height space. The quadratic brute force and this share every line of arithmetic; the only difference is that this one keeps what it already computed.

If this problem will not click, solve Diameter of Binary Tree first. It has the identical return-versus-record split with edges instead of sums, and without negative numbers to reason about at the same time.