LeetCode · #124

Binary Tree Maximum Path Sum Solution

Given a binary tree, find the maximum path sum. A path can start and end at any node — it doesn't need to pass through the root.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #124

🏗️

Pattern

Post-order DFS — single-path vs split-path

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A path does not need to pass through the root. The path sum is the sum of node values in the path. Return the maximum path sum of any non-empty path.

Example

 Input: -10
        /   \
       9    20
           /  \
          15   7
Output: 42 // Path: 15 → 20 → 7 = 42 

Constraints

• 1 ≤ number of nodes ≤ 3 × 10⁴ • -1000 ≤ Node.val ≤ 1000

Section Two · Approach 1

Brute Force — O(n²)

For every pair of nodes, compute the path sum between them. O(n²) pairs, each requiring O(n) traversal. Far too slow.

Section Three · Approach 2

Post-Order DFS — O(n)

At each node, compute the max sum of a path that goes through this node — possibly using both children (split path). But return to the parent only the best single-branch path (can't split upward). Track a global maximum.

💡 Mental model: Each node asks its children: "What's the best single-arm path you can offer me?" It then considers three options: (1) just itself, (2) itself + left arm, (3) itself + right arm, (4) itself + both arms (split — can't go upward). Options 1-3 are reportable to the parent. Option 4 is only used to update the global max.

Algorithm

Recursive function returns the max single-path sum starting from this node going downward.
At each node:
leftGain = max(0, dfs(left)) — take left branch only if positive.
rightGain = max(0, dfs(right)) — same for right.
splitPath = node.val + leftGain + rightGain — path through this node using both sides.
Update globalMax = max(globalMax, splitPath).
Return: node.val + max(leftGain, rightGain) — best single-arm to offer parent.

🎯 Why max(0, ...)?:

If a subtree's best path is negative, don't include it — it only hurts the sum.
Setting gain to 0 effectively "prunes" that branch. This handles negative values naturally.

Key distinction — split vs single:

The split path (left + node + right) can be the answer but cannot be extended upward (you can't go left-node-right-parent — that's not a valid path).
So we only return the best single branch to the parent while updating the global max with the split option.

Section Four · Trace

Visual Walkthrough

Post-order DFS — tree [-10, 9, 20, null, null, 15, 7]

Section Five · Implementation

Code — Java & Python

Java — Post-order DFS

 class Solution {
int globalMax = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
        dfs(root);
return globalMax;
    }
private int dfs(TreeNode node) {
if (node == null) return 0;
int leftGain  = Math.max(0, dfs(node.left)); // prune negatives int rightGain = Math.max(0, dfs(node.right));
// Split path through this node (can't extend upward)
globalMax = Math.max(globalMax, node.val + leftGain + rightGain);
// Return best single arm to parent return node.val + Math.max(leftGain, rightGain);
    }
}

Python — Post-order DFS

 class Solution:
def maxPathSum(self, root) -> int:
        self.global_max = float('-inf')
def dfs(node):
if not node: return 0
left_gain  = max(0, dfs(node.left))
            right_gain = max(0, dfs(node.right))

            self.global_max = max(self.global_max,
                                  node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)

        dfs(root)
return self.global_max

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Post-order DFS	O(n)	O(h) — call stack

Each node visited once.:

At each node we do O(1) work — compare gains, update global max. Total: O(n).
Space is the recursion depth = tree height.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All negative	`[-3,-2,-1]`	Max path is the single largest node (-1). max(0,...) prunes, but globalMax still considers each node alone.
Single node	`[5]`	Split = 5+0+0 = 5. Correct.
Negative root, positive children	`[-10,9,20]`	Split through root may be suboptimal. globalMax tracks child paths independently.

⚠ Common Mistake: Returning the split path (left + node + right) to the parent. A split path through this node uses both branches — it can't be extended upward because that would create a fork. Only return the best single-arm path: node.val + max(leftGain, rightGain).

← Back to Trees problems

LearningTree

LC 124 · Binary Tree Maximum Path Sum — Solution & Explanation | DSA Guide