Binary Tree Maximum Path Sum — Blind 75 practice

Problem

A path in a binary tree is any sequence of nodes where consecutive nodes are connected by an edge, each node appears at most once, and the path need not pass through the root or reach a leaf.
Given the root, return the largest possible sum of a path's values. A path has at least one node, so an all-negative tree still answers with its least-bad node.

Examples

Example 1:
Input: root = [1,2,3]
Output: 6

Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: 15 + 20 + 7 — the best path never touches the root.

Example 3:
Input: root = [-3]
Output: -3

Example 4:
Input: root = [2,-1]
Output: 2

Constraints

1 <= number of nodes <= 3 * 10^4
-1000 <= Node.val <= 1000

Prerequisites

Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree.
Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.

How to think about it

1. Two Roles for Every Node Optimal

Intuition

Each node plays two parts, and keeping them apart is the entire problem. As a PASS-THROUGH it hands its parent a chain: itself plus at most ONE child's contribution, because a path cannot fork and still continue upward. As a SUMMIT it may join both children and go no higher — that is where the best answer might live. So the recursion returns the pass-through value while a running best records every summit. A negative contribution is dropped to zero: a path may simply decline to include it.

Algorithm

1. An empty node contributes nothing.
2. Take each child's contribution, clamped at zero.
3. The summit through this node is its value plus both contributions — offer that to the running best.
4. Return this node's value plus the LARGER single contribution, which is what its parent can use.

Time & Space

Time O(n). Space O(h). Seed the best at negative infinity so an all-negative tree still answers with its least-bad node.