124 · Binary Tree Maximum Path Sum

LC 543 with two additions: the returned value is clamped at zero, because a negative branch is simply not used, and the recorded value may be a single node. The clamp is the entire difficulty.

1 — The problem

A path is any sequence of nodes connected by edges, going in any direction but visiting no node twice. Return the largest sum along any such path. Values may be negative — that is the whole problem.

The sub-variant C skeleton is unchanged. Only the two quantities are redefined:

	543. Diameter	124. Max Path Sum
Returned	`1 + max(L, R)`	`val + max(L, R)`, with L and R clamped at 0
Recorded	`L + R`	`val + L + R`, same clamped L and R
Identity	`0`	`0` — and it doubles as the clamp floor
`best` starts at	`0`	`Integer.MIN_VALUE`

That last row is not a detail. The answer can be negative — on a tree of a single node valued −3, the answer is −3 — so a best starting at 0 would return 0, a path that does not exist.

1.1 What the clamp means

Math.max(0, gain(child)) reads as an arithmetic trick and is actually a decision: if a branch would lower the total, do not walk into it. A path is allowed to stop at any node, so declining a branch is always legal, and its contribution is 0 rather than negative.

The clamp belongs on the child's contribution, not on the node's own value. The node is on the path by construction — nd.val is added unconditionally, even when it is negative. Clamping the node itself would let paths skip over their own nodes, which is not a path.

2 — Watching a branch get declined

The left branch of the root is worth −9. Watch line 3 turn that into 0 at the root — the −9 subtree is not part of any best path and the recursion stops pretending it might be.

The winning path 15 – 20 – 7 turns at node 20 and never reaches the root. Node 20 records 42 and returns 35 — and 35 is what the root sees, because the root can only extend one side, not both.

2.1 Three places the sign matters

Line	Clamped?	Consequence of getting it wrong
`L` and `R` from children	Yes	Without the clamp, a bad subtree drags down a path that could simply have avoided it. Wrong answer on any tree with negatives.
`nd.val` in the recorded sum	No	Clamping it would allow a path to pass through a node without paying for it. Overestimates.
`best`'s initial value	No — `MIN_VALUE`	Starting at 0 returns 0 for all-negative trees, and 0 is not a path.

All three are the same question asked in three places: is the empty path allowed here? For a child's contribution, yes. For the node itself and for the final answer, no.

3 — Complexity and edge cases

Time O(n), space O(h). One postorder pass.
Single node, negative value: the answer is that value. This is the test that catches a best = 0 initialisation.
All values negative: the answer is the single largest (least negative) node, because every clamp fires and every record reduces to nd.val + 0 + 0.
Overflow: with 3 × 10⁴ nodes at ±1000 the worst case fits comfortably in int. If the bounds grow, the recorded sum is the expression that overflows first.
Common bug: returning nd.val + L + R — the recorded value — instead of nd.val + max(L, R). That hands the parent a path with two loose ends, which is the exact error LC 543 exists to teach.
Common bug: clamping with Math.max(0, nd.val + …) — the clamp goes on each child's gain before the node's value is added, not after.

4 — Reference implementation

Java 21Clamped gain with a recorded maximum, matching the visualizer.13 lines

private int best;

public int maxPathSum(TreeNode root) {
    best = Integer.MIN_VALUE;         // the answer may be negative
    gain(root);
    return best;
}

private int gain(TreeNode nd) {
    if (nd == null) return 0;
    int L = Math.max(0, gain(nd.left));    // decline a losing branch
    int R = Math.max(0, gain(nd.right));
    best = Math.max(best, nd.val + L + R);  // record: turns here, uses both sides
    return nd.val + Math.max(L, R);        // return: continues up, one side only
}