TreeHardO(n) time · O(h) space

Maximum Path Sum

Mahabharata — The Greatest Victory Path — The Maximum Sum Along Any Path in the Tree

कोई भी पथ — अधिकतम योग। हर नोड पर: left + right + val — वैश्विक अधिकतम में जोड़ो॥

*Any path — maximum sum. At each node: left + right + val — update global maximum.*

The Story

Find the maximum sum of any path in a binary tree. A path is any sequence of nodes where each adjacent pair is connected by an edge; it can start and end anywhere.

For `[-10,9,20,null,null,15,7]`: max path = 15+20+7=42. For `[1,2,3]`: max path = 2+1+3=6.

**The key insight:** The maximum path can 'bend' at any node — going into left subtree and right subtree and through the current node.

**gain(node):** returns the maximum gain from one side (for the parent to use) - `gain(null) = 0` (contributing 0) - Prune negative gains: `max(0, gain(left))`, `max(0, gain(right))` - **Update global max:** `max = Math.max(max, root.val + leftGain + rightGain)` (path through current node) - **Return to parent:** `root.val + max(leftGain, rightGain)` (only one direction; can't bend at parent)

```java int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { gain(root); return max; } int gain(TreeNode root) { if (root == null) return 0; int leftGain = Math.max(0, gain(root.left)); // Ignore if negative int rightGain = Math.max(0, gain(root.right)); // Ignore if negative max = Math.max(max, root.val + leftGain + rightGain); // Path through root return root.val + Math.max(leftGain, rightGain); // Best single arm to parent } ```

Trace `[-10,9,20,null,null,15,7]`: - gain(9)=9, max updated to 9 - gain(15)=15, max=15 - gain(7)=7, max=15 - gain(20): left=15,right=7. max=max(15, 20+15+7=42)=42. return 20+15=35 - gain(-10): left=max(0,9)=9,right=max(0,35)=35. max=max(42,-10+9+35=34)=42. return -10+35=25 - Answer=42 ✓

The Try-All-Paths Approach

For each node as path endpoint, try all paths through it. O(n²) or worse.

java

// O(n²): for each node compute max gain separately
// The single-pass gain() function is already optimal

The Gain-Function Single-Pass Wisdom

gain(root): prune negative gains. Update max = max(max, val+leftGain+rightGain). Return val+max(leftGain,rightGain) for parent.

java

int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    gain(root);
    return max;
}

int gain(TreeNode root) {
    if (root == null) return 0;
    int left = Math.max(0, gain(root.left));
    int right = Math.max(0, gain(root.right));
    max = Math.max(max, root.val + left + right);
    return root.val + Math.max(left, right);
}

Step-by-Step Walkthrough

[2,-1]: gain(-1)=max(0,0)+max(0,0)+(-1). left=0,right=0. max=-1. return -1.
gain(2): left=max(0,-1)=0, right=0. max=max(-1,2+0+0)=2. return 2. Answer=2 ✅

Deep Insight

**Three patterns from one function:** gain() simultaneously: 1. Returns the best 'arm' to the parent (for paths continuing upward) 2. Updates global max for paths that 'bend' at the current node 3. Prunes negative subtrees (gain 0 if negative — don't include)

**max(0, gain):** If a subtree has a negative total gain, it's better to start/end the path here rather than extend into that subtree. This is the pruning step.

**Integer.MIN_VALUE initialization:** Handles trees with all-negative values (the answer is the largest single node value). DO NOT initialize max=0.

**Generalization:** This same pattern appears in 'Maximum Sum Circular Subarray' and other 'bend-at-any-point' problems.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(h)	Compute gain from scratch at each node
Optimal	O(n)	O(h)	Single post-order pass with global max update

Pattern Recognition

✅ Max path sum: gain function with global max
✅ Prune negative: max(0, gain(subtree))
✅ Update max: val + leftGain + rightGain (bend point)
✅ Return: val + max(left, right) (one arm to parent)
✅ Init max = Integer.MIN_VALUE (not 0!)

**LeetCode Trigger Phrases:**
→ "binary tree maximum path sum"
→ Any path (can bend at node)
→ Prune negative subtrees

Bhagavad Gita 2.38

सुखदुःखे समे कृत्वा लाभालाभौ जयाजयौ। ततो युद्धाय युज्यस्व नैवं पापमवाप्स्यसि॥

Having made pleasure and pain, gain and loss, victory and defeat the same, engage in battle. Thus you will incur no sin.

Connection: The Maximum Path Sum algorithm seeks the greatest victory (maximum gain) through the tree, pruning away negative branches that would diminish the path's power. Like the Gita's warrior who treats gain and loss equally in principle but must choose the path of action, the algorithm identifies which subtree contributions increase the path sum and includes them, ignoring those that would reduce it. The 'bend at any node' freedom represents the unbounded nature of the search for excellence.