Binary Tree Maximum Path Sum

Difficulty: Hard

Problem

A path is any sequence of connected nodes where each node appears at most once — it does NOT need to pass through the root, and it does NOT need to end at leaves. Node values can be NEGATIVE. Return the maximum possible sum of values along any path containing at least one node.

Example

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The best path is 15 → 20 → 7 = 42. It skips the root entirely — extending up through -10 would only lose value.

Brute-force approach

Enumerating all paths is exponential — there is no sane brute force. The one-pass gain recursion below is both the intuitive and the optimal solution.

Optimal approach

Key insight: Diameter counted edges; here we sum values. Each call returns the best straight chain DOWN, records the best bend THROUGH itself — and drops any branch that would lose money.

One postorder pass: each node computes its best downward chain (gain), records the best bend (node + both clamped gains) into a global best, and returns the chain to its parent.

Steps

1. Track a global best, starting at −∞
2. gain(null) = 0
3. At each node: L = max(gain(left), 0), R = max(gain(right), 0)
4. Record the bend: best = max(best, node.val + L + R)
5. Return the chain: node.val + max(L, R)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree