Binary Tree Maximum Path Sum — LC 124 Hard DFS Interview Classic

Problem Statement#

LeetCode 124 — Binary Tree Maximum Path Sum | Difficulty: Hard

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can only appear in the sequence at most once. The path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Constraints:

• The number of nodes is in the range [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

Input:  root = [1,2,3]
Output: 6
Explanation: Path 2 → 1 → 3 with sum 2 + 1 + 3 = 6

Input:  root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: Path 15 → 20 → 7 with sum 15 + 20 + 7 = 42

Why This Problem Matters#

Binary Tree Maximum Path Sum is one of the hardest and most frequently asked tree problems at FAANG. Amazon, Google, and Facebook include it in their interview pools because it tests two distinct skills simultaneously: global state tracking (the maximum path seen so far) and local return value computation (the best single-branch gain to offer the parent). Candidates who fail this problem typically confuse these two responsibilities.

The key distinction — a node can use both children for the global max update, but can only pass one branch upward to the parent — is a subtle design constraint that requires careful thought. Missing it produces incorrect results for any path that "bends" through an internal node.

The Core Insight#

For each node, a path can:

1. Pass through the node using both left and right subtrees (a "bent" path — cannot be extended further upward)
2. Continue upward by extending through exactly one subtree plus the current node

The DFS function does two things at each node:

1. Update global max: node.val + max(left_gain, 0) + max(right_gain, 0) — uses both branches
2. Return to parent: node.val + max(left_gain, right_gain, 0) — uses at most one branch

Clamping gains at 0 (max(gain, 0)) handles negative subtrees: never extend a path into a subtree that would decrease the sum.

Visual Dry Run#

Tree: [-10, 9, 20, null, null, 15, 7]

Answer: 42.

Solution (Optimal)#

class Solution:
    def maxPathSum(self, root) -> int:
        self.max_sum = float('-inf')
 
        def dfs(node):
            if not node:
                return 0
 
            # Gain from left and right subtrees (clamp negatives to 0)
            left_gain = max(0, dfs(node.left))
            right_gain = max(0, dfs(node.right))
 
            # Update global max: path bends through this node using both sides
            self.max_sum = max(self.max_sum, node.val + left_gain + right_gain)
 
            # Return max single-branch gain to parent
            return node.val + max(left_gain, right_gain)
 
        dfs(root)
        return self.max_sum

var maxPathSum = function(root) {
    let maxSum = -Infinity;
 
    function dfs(node) {
        if (!node) return 0;
 
        // Clamp negative gains to 0 — never extend into a losing subtree
        const leftGain = Math.max(0, dfs(node.left));
        const rightGain = Math.max(0, dfs(node.right));
 
        // Candidate path through this node (bent — cannot extend upward)
        maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
 
        // Return best single-branch extension to parent
        return node.val + Math.max(leftGain, rightGain);
    }
 
    dfs(root);
    return maxSum;
};

Time: O(n) — each node visited exactly once Space: O(h) — recursion stack; O(log n) for balanced tree, O(n) for skewed

Common Mistakes#

• Returning node.val + left_gain + right_gain to the parent (using both branches) — a path cannot extend upward if it already bends at this node
• Forgetting to clamp gains to 0 — negative subtrees should not be included
• Initializing max_sum = 0 instead of -infinity — fails for all-negative trees where the answer is a single negative node
• Confusing the global max update with the return value — these two responsibilities must stay separate

Interview Tips#

• Explicitly state the two responsibilities before coding: "update global max" and "return one branch to parent"
• Draw a tree where a path bends through an internal node to illustrate why you return only one branch
• Mention that this generalizes to any "max path in tree" problem — the pattern is always: global update uses both sides, return uses one side
• Initialize the global max to node.val of some valid single node, or to -infinity before the DFS

Follow-up Questions#

• What if path length must be exactly k nodes? Use a DFS that tracks the path length alongside the sum, with pruning.
• What if negative nodes cannot be included? Change the clamping: instead of max(0, gain), only include a node if its subtree sum is positive.
• How would you return the actual path, not just the sum? Track the path nodes in the DFS and record the path whenever you update the global max.
• What if the tree is an n-ary tree (multiple children)? Same pattern: update global max using all children's gains, return only the best single child gain.
• What is the relationship to Diameter of Binary Tree (LC 543)? LC 543 maximizes path length (number of edges); LC 124 maximizes path sum. The code structure is identical — only the values being tracked differ.

Key Takeaways#

• The DFS function has two distinct jobs: update the global max (both branches) and return the best single branch to the parent
• Clamping gains to 0 (max(0, gain)) handles negative subtrees — never extend a path that reduces the sum
• Initialize the global max to negative infinity to correctly handle all-negative trees
• Global max update: node.val + left_gain + right_gain (path bends here, cannot extend up)
• Return value: node.val + max(left_gain, right_gain) (path continues in one direction only)
• Time O(n), space O(h) — optimal for this problem
• This "two responsibilities" pattern (global update vs. return value) applies to LC 543, LC 687, and many other tree path problems