Maximum Path Sum

Problem

Find the maximum path sum in a binary tree where a path is any sequence of nodes connected by edges (doesn’t need to start/end at root).

Example: [1,2,3] → max sum is 1+2+3 = 6 (all nodes)

Note: Negative values should be ignored; pick 0 (empty path) instead.

---

Solution: DFS with Node State

Track two states per node:

• Max through node: Best path that goes through this node (both subtrees included)
• Max from node: Best path that extends downward (either left or right)

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            
            # Max path from left and right subtrees (ignore negatives)
            lsum = max(0, dfs(node.left))
            rsum = max(0, dfs(node.right))
            
            # Max path through this node (including both children)
            self.ans = max(self.ans, node.val + lsum + rsum)
            
            # Return max we can extend upward (one child only)
            return node.val + max(lsum, rsum)
        
        dfs(root)
        return self.ans

Time: O(n)
Space: O(h) — recursion depth

---

How It Works

Step-by-Step Example

Tree:

      -10
      /  \
     9   20
        /  \
       15   7

DFS(9): lsum=0, rsum=0 → ans=max(-inf, 9)=9, return 9
DFS(15): lsum=0, rsum=0 → ans=max(9, 15)=15, return 15
DFS(7): lsum=0, rsum=0 → ans=max(15, 7)=15, return 7
DFS(20): lsum=15, rsum=7 → ans=max(15, 20+15+7)=42, return 20+15=35
DFS(-10): lsum=9, rsum=35 → ans=max(42, -10+9+35)=42, return -10+35=25

Answer: 42 (path: 15 → 20 → 7)

---

Why This Works

Key insight: For each node, decide:

1. Is this node the turning point? → Include both children (update global max)
2. Should we extend upward? → Pick best child to extend to parent

By tracking both, we ensure every possible path is evaluated without needing to reconstruct it.