−∞
globalBest
Find the maximum-sum path between any two nodes in a binary tree. A single post-order DFS returns each node's best downward gain (negatives clamped to 0) while a global best tracks the full through-node path — linear time, one pass.
A path is any sequence of connected nodes (parent↔child edges) with no node repeated; it need not pass through the root. Return the maximum sum of node values over all such paths. For [-10,9,20,null,null,15,7] the answer is 42 — the path 15 → 20 → 7 (the root -10 only drags the total down, so the best path skips it).
val + max(left, right)), because a parent can only attach to you through a single branch. But the best path that peaks at this node may use both children: val + left + right. Record that "through" sum into a global best; never return it upward.leftGain and rightGain from the children beforetouching this node — you can't score a node without its subtrees' answers.leftGain = max(0, gain(left)) (same for right). A branch that sums negative is simply not taken — zero is always available by stopping at this node.best = max(best, val + leftGain + rightGain). This is the path that bends through this node using both sides — its highest possible point.return val + max(leftGain, rightGain). The parent can only continue through one side, so hand back a straight-line gain, never the bent through-path.0 instead — a losing branch should be dropped, not subtracted. (2) Returning the through-sum upward: the answer that uses left + right bends at this node and cannot extend to the parent. So the recursion returns the one-sided value while the global best absorbs the two-sided value.Time is O(n) — each node is entered exactly once. Extra space is O(h) for the call stack, where h is the tree height: O(log n) if balanced, O(n) in the worst case (a degenerate "linked-list" tree).
val + max(0, leftGain, rightGain) to its parent, while we update globalBest with the full through-node path val + leftGain + rightGain.class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function maxPathSum(root: TreeNode | null): number {
let best = -Infinity; // global answer (any node may start it)
// returns the max DOWNWARD gain of a path that starts at `node`
function gain(node: TreeNode | null): number {
if (node === null) return 0; // missing child contributes nothing
const left = Math.max(0, gain(node.left)); // clamp: skip negative branches
const right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right); // path THROUGH node (can't go up)
return node.val + Math.max(left, right); // extend to parent via ONE side only
}
gain(root);
return best;
}best starts at -Infinity, not 0 — the optimal path might consist of a single negative node (e.g. a tree of all negatives), and 0 would wrongly beat it.null child returns 0 gain. Combined with the Math.max(0, …)clamp at the parent, this cleanly means "a missing or losing branch adds nothing."left and right are each forced to be ≥ 0. This is the single most-missed line: a negative subtree should be excluded from the path, which is exactly what taking max(0, gain) does.val + left + right is the best path whose highest node is the current one, using both branches. We fold it into best but never return it.val + max(left, right) — a straight downward line, not the bent path. After gain(root) finishes, best holds the answer.O(n) time (each node visited once) and O(h) stack space, where h is the tree height — O(log n) balanced, O(n) worst case.best to -Infinity and not 0?" A tree of all-negative values has a negative answer; 0 would shadow it. The single largest (least-negative) node must remain a candidate.best when you update it, then walk down from that node.leftDepth + rightDepthglobally. Same post-order "return one, record another" template.| max path between any two nodes | post-order DFS + global best |
| answer can bend at a node | record val+left+right, return val+max(left,right) |
| negative subtree branch | clamp with max(0, gain(child)) |
| all-negative values possible | init best = -Infinity |
let best = -Infinity;
function gain(node) {
if (!node) return 0;
const l = Math.max(0, gain(node.left));
const r = Math.max(0, gain(node.right));
best = Math.max(best, node.val + l + r); // through node
return node.val + Math.max(l, r); // upward: one side
}
gain(root);
return best;val + max(leftGain, rightGain) — a parent can only attach through a single branch.