# Binary Tree Maximum Path Sum

- **Canonical ID**: `binary-tree-maximum-path-sum`
- **Canonical URL**: https://dsacheatsheet.com/problems/binary-tree-maximum-path-sum
- **Difficulty**: hard
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/binary-tree-maximum-path-sum/

## 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

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Single post-order pass; clamping negative child contributions embodies Kadane’s principle on tree paths.

## 3. Minimal Idiomatic Code

### Python
```python
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
```

### TypeScript
```typescript
export function maxPathSum(root: TreeNode | null): number {
  let best = root ? root.val : 0;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const lg = Math.max(0, gain(node.left));
    const rg = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + lg + rg);
    return node.val + Math.max(lg, rg);
  };
  gain(root);
  return best;
}
```

### C++
```cpp
int maxPathSum(TreeNode* root) {
    int best = root->val;
    auto gain = [&](auto& self, TreeNode* n) -> int {
        if (!n) return 0;
        int lg = max(0, self(self, n->left));
        int rg = max(0, self(self, n->right));
        best = max(best, n->val + lg + rg);
        return n->val + max(lg, rg);
    };
    gain(gain, root);
    return best;
}
```

### Java
```java
int best;
int maxPathSum(TreeNode root) {
    best = root.val;
    gain(root);
    return best;
}
int gain(TreeNode n) {
    if (n == null) return 0;
    int lg = Math.max(0, gain(n.left));
    int rg = Math.max(0, gain(n.right));
    best = Math.max(best, n.val + lg + rg);
    return n.val + Math.max(lg, rg);
}
```

### Go
```go
func maxPathSum(root *TreeNode) int {
    best := root.Val
    var gain func(*TreeNode) int
    gain = func(n *TreeNode) int {
        if n == nil { return 0 }
        lg := max(0, gain(n.Left))
        rg := max(0, gain(n.Right))
        if n.Val+lg+rg > best { best = n.Val + lg + rg }
        return n.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)`.