Binary Tree Maximum Path Sum
Find the maximum sum over any path (any node to any node, no revisits).
Open on LeetCode ↗Intuition
Like diameter, but weighted and with negatives. Each node answers two different questions: 'best downward path starting here' (what the parent can use — one branch only) and 'best path bending here' (left gain + node + right gain — a candidate answer). Negative branches contribute 0: better to not extend.
The signature of this family is that what you return is not what you're computing. A path may bend at its topmost node and use both children, but a node can only contribute a straight branch to its parent. So the recursion returns the best downward branch while a separate variable records the best bend seen anywhere. Whenever the global answer has a different shape from the recursive contract, split them like this — diameter-of-binary-tree is the same problem with edge counts.
Approach
Gain = usable path
gain(node) = node.val + max(gain(left), gain(right), both clamped at 0). A parent can extend through only one child.
Bend = candidate
At each node, leftGain + node.val + rightGain uses both branches — legal as a full path, illegal to pass upward. Track its max globally.
Clamp negatives to zero
max(gain, 0) implements 'drop a branch that hurts' — the crux with negative values.
Solution & live demo
Common pitfalls
Returning the bent path to the parent
return node.val + l + r
return node.val + max(l, r)
A path that already used both children can't be extended upward — going to the parent would visit the node twice. The parent may only receive a single descending arm, so exactly one child is chosen. The both-children sum is only ever recorded in self.best.
Not clamping negative gains at zero
l = gain(node.left) r = gain(node.right)
l = max(gain(node.left), 0) r = max(gain(node.right), 0)
A subtree that sums negative should simply be excluded — the path can stop at the current node. Without the clamp a -25 child drags down an otherwise-optimal path.
Initialising best to zero
self.best = 0
self.best = float("-inf")On an all-negative tree like [-3] the answer is -3, since a path must contain at least one node. Seeding at 0 reports an empty path instead.
Edge cases
Clamps make gains 0, but the bend at each single node still records node.val — the answer is the largest (least negative) node.
Bend = its value.