Binary Tree Maximum Path Sum

hardTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(H)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Post-order DFS computes the maximum downward *single-branch* gain (`max(0, dfs(child))` — clamp negatives to `0`). At each node `u`, evaluate splitting through `u` (`u.val + leftGain + rightGain`) against the global max, then return `u.val + max(leftGain, rightGain)` upward.

2. Complexity Bounds & Proof

Single post-order pass; clamping negative child contributions embodies Kadane’s principle on tree paths.

3. Minimal Idiomatic Code

def maxPathSum(root: Optional[TreeNode]) -> int:
    best = root.val
    def gain(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        lg = max(0, gain(node.left))
        rg = max(0, gain(node.right))
        best = max(best, node.val + lg + rg)
        return node.val + max(lg, rg)
    gain(root)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Returning `u.val + leftGain + rightGain` to the parent creates an invalid forked path (paths cannot branch upward!). - Initializing global `best = 0` fails when all nodes are negative; initialize `best = root.val` or `-inf`.
Follow-ups:- House Robber III uses a similar post-order pair `(withNode, withoutNode)`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Diameter of Binary Tree (O(N))Maximum Subarray (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.