Binary Tree Maximum Path Sum
WHAT IT SAYS
Find the maximum sum over all paths in the tree, where a path is any sequence of connected nodes and values may be negative.
WHAT IT'S REALLY ASKING
"Every node plays two different roles and must never confuse them: as an APEX it may join both of its arms into one bent path, but as an ARM offered to its parent it may extend only one way — and if its best arm is worth less than nothing, the parent is better off without it. Which role does each number in your function serve?"
Enumerate paths between all pairs of nodes
O(n^2) pairs, each path up to O(n) long — cubic in the worst caseFor every pair of nodes, find the path connecting them (walk up to the lowest common ancestor and down), sum its values, and keep the best. Or equivalently: from every node, DFS outward in all directions collecting path sums.
WHERE THE WORK IS WASTED — Paths overlap massively and the enumeration pays full price for every overlap. Two paths sharing a fifty-node trunk are summed independently, fifty additions each, though they differ in a single leaf. The tree structure has already factored those shared trunks — each edge exists once — and pair-enumeration multiplies them back out. Worse, most of the pairs are noise: the best path is determined by local decisions (extend or stop) that never required naming two endpoints at all.
An arm that sums below zero is worth exactly zero.
Start with the diameter's skeleton, because it transfers whole: every path has a unique apex — its highest node — and from the apex it descends as at most two arms that share no edges. So the global answer is a per-apex question: node value, plus the best downward arm into the left, plus the best downward arm into the right. Negatives change one thing, and it is the same thing Kadane's algorithm discovered in arrays: a contribution you are free to decline should be declined when it is negative. An arm is optional — a path is allowed to bend at the apex and simply not extend into a child. So the arm's worth is max(bestArm(child), 0): if the best the subtree can offer still drags the sum down, the correct amount to take is nothing. Clamping at zero is not a trick; it is the definition of 'optional' applied to arithmetic. The apex itself is NOT optional — a path must contain its apex, so the node's own value participates unclamped, and an all-negative tree correctly answers with its least-negative single node. Now the two roles, stated exactly, because every wrong answer to this problem confuses them. As APEX, a node records value + leftArm + rightArm into a running global best — the bent path dies here and is a candidate answer. As ARM, the node returns value + max(leftArm, rightArm) to its parent — one direction only, because a path entering from above and using both children would visit this node twice. The recorded quantity and the returned quantity are different numbers serving different masters, computed side by side in the same post-order visit.
One post-order pass, record the apex, return the arm
O(n) time, O(h) stack spaceRecurse: null contributes 0. Compute leftArm = max(recurse(left), 0) and rightArm = max(recurse(right), 0). Update the global best with node.val + leftArm + rightArm. Return node.val + max(leftArm, rightArm). Initialise the best to negative infinity, not zero — an all-negative tree must be allowed to answer negatively.
Record the Apex, Return the Arm
YOU'LL SEE IT AGAIN WHEN
- The answer is a path free to start and end anywhere, so it bends at a unique apex — measure the bend at every node.
- Contributions are optional and possibly negative, so each is clamped at zero at the moment of inclusion, exactly like Kadane's restart.
- The value propagated upward is structurally different from the value recorded — one arm versus both — and the recursion must keep them separate.