Binary Tree Maximum Path Sum

Problem

Power-grid planners evaluate contingency paths across a network shaped as a binary tree: each node carries a load value (possibly negative when a segment draws power), and a viable contingency path is any connected chain of nodes, starting and ending anywhere, following parent-child links. Given the root, find the maximum possible sum of node values along any such path.

Example 1:

Input: root = [5,6,3,2,4,null,8]
Output: 26
Explanation: the path 2 -> 6 -> 5 -> 3 -> 8 sums to 26 - it bends at the root, drawing the best leg from each subtree.

Example 2:

Input: root = [-8,3,7,9,-4,null,0,null,null,null,null,null,5]
Output: 16
Explanation: the path 3 -> 9 joins the path 0 -> 5 through -8: 12 + 12 + (-8) = 16, outweighing any single-subtree path.

Example 3:

Input: root = [2,-1,-3]
Output: 2
Explanation: both children are negative - the best path is the root alone.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10^4].
• -1000 <= Node.val <= 1000

Tree 1:        5           gains:  2->2   4->4
              / \                  6->6+max(2,4)=10
             6   3                 8->8   3->3+8=11
            / \   \                5 -> bend 5+10+11 = 26  <- best
           2   4   8
 
Tree 2:      -8
            /  \
           3    7
          / \    \
         9  -4    0
                   \
                    5
best bends: 9 | 3+9=12 | 0+5=5 | 7+5=12 | -8+12+12=16  <- best

Solution Breakdown

Approach - postorder recursion that returns a downward leg while tracking bends in a running best.

The whole problem lives in one distinction: a path bending at a node may use both of its subtrees, but any path extending upward past the node may use at most one. So the recursion carries two different quantities. The return value (the "gain") is the best path that starts at the node and descends into at most one child: node.val + max(left_gain, right_gain) - and because no path is obligated to drag a negative child along, each child's gain is clipped with max(child_gain, 0) before use. The tracked value is the best bend at the node: node.val + left_clipped + right_clipped, folded into a running best initialized to negative infinity (trees of all-negative values are legal inputs, and a single node can be the answer). The bend is folded, never returned - handing it upward would let a parent fork into both subtrees, which is not a path.

The traversal must be postorder because both quantities need the children's gains first. Trace tree 1 (5, (6, (2, 4)), (3, (-, 8))): gains settle bottom-up - 2 -> 2, 4 -> 4, 6 -> 6 + max(2, 4) = 10 with a bend of 12; 8 -> 8, 3 -> 3 + 8 = 11 with a bend of 11; the root bends 5 + 10 + 11 = 26, the final answer, while returning the leg 5 + 11 = 16 that no caller uses. Tree 2 shows why negative roots still join paths: -8's children bend at 12 and 12, so the through-path -8 + 12 + 12 = 16 beats every single-subtree path. And [2, -1, -3] shows the clipping: both children's gains read as 0, the bend is 2, and the answer is the root alone.

Edge cases - all-negative trees: best starts at -inf so the least-negative single node wins; a node with one missing child just uses the present child's clipped gain (missing reads 0); the single-node tree folds its own value with 0 + 0 legs.

Complexity - O(n) time, every node visited once with constant folding work; O(h) space for the recursion stack - O(log n) balanced, O(n) on a skewed tree. No additional structures are needed; the running best is a scalar.