Leetcode 124. Binary Tree Maximum Path Sum

Let's understand what we're being asked to do. We have a binary tree where each node contains a value (which can be negative), and we need to find the maximum sum of any path.

A path is a sequence of connected nodes where each node appears at most once. The path can start and end at any nodes - it doesn't have to go through the root!

For example, in a tree with values [1, 2, 3] where 1 is root with children 2 and 3, the path 2 -> 1 -> 3 has sum 2+1+3 = 6. But we could also consider just the single node path 3 with sum 3, or the path 1 -> 3 with sum 4.

Critical constraint: When all values are negative (like [-3, -2, -1]), we must still return a valid path. The best choice would be the single-node path with the least negative value (in this case, -1).

Edge cases to consider: What if the tree has only one node? What if we have a path that goes down one subtree, through a node, and down another subtree? What if including a parent node actually decreases our sum?

At each node, we face a decision: should we extend a path from one of our subtrees through ourselves, or should we connect paths from both subtrees through ourselves?

For example, if our left subtree offers a path sum of 10, our right subtree offers 15, and our value is 5, we could:

• Extend left: 10 + 5 = 15
• Extend right: 15 + 5 = 20
• Connect both: 10 + 5 + 15 = 30

The key insight is that a connecting path (using both subtrees) cannot be extended further upward, but an extending path (using one subtree) can be part of a larger path.

This means at each node, we need to track TWO different values:

1. The maximum path sum that passes through this node (potentially connecting both subtrees)
2. The maximum path sum we can contribute upward to our parent (can only use one subtree)

The global answer is the maximum of all "passing through" sums, but what we return to our parent is the "contribute upward" value.

Think of each node as a bridge between two islands (left and right subtrees). You can:

• Walk across the bridge and continue to one island (extending path)
• Walk from one island, across the bridge, to the other island (connecting path - but now you're stuck, can't go further)

As you explore the tree, you're constantly asking: "What's the best path I can make here?" and "What's the best contribution I can offer to my parent?"

When values are negative, you might choose to not include a subtree at all (contributing 0 is better than adding a negative sum).

Use a recursive depth-first search (DFS) to explore the tree. At each node, calculate the maximum path sum that can be contributed upward (using at most one subtree) and the maximum path sum passing through this node (potentially using both subtrees). Track the global maximum across all nodes. For each subtree, we take the maximum of its contribution or zero (to handle negative sums). Return the best single-path contribution upward while updating the global maximum with the best connecting path at each node.

def max_path_sum(root):
    """
    Find maximum path sum in binary tree using DFS.
    Path can start and end at any nodes.
    """
    # Track global maximum across all paths
    max_sum = [float('-inf')]
    
    def dfs(node):
        # Base case: empty node contributes 0
        if not node:
            return 0
        
        # Recursively get max contribution from left subtree
        left_contribution = dfs(node.left)
        # Recursively get max contribution from right subtree
        right_contribution = dfs(node.right)
        
        # Take max of subtree contribution or 0 (ignore negative paths)
        left_max = max(left_contribution, 0)
        right_max = max(right_contribution, 0)
        
        # Calculate path sum passing through current node (using both subtrees)
        path_through_node = node.val + left_max + right_max
        
        # Update global maximum with path through this node
        max_sum[0] = max(max_sum[0], path_through_node)
        
        # Return best single-path contribution upward (can only use one subtree)
        return node.val + max(left_max, right_max)
    
    # Start DFS from root
    dfs(root)
    
    # Return the global maximum path sum found
    return max_sum[0]

• Post-order DFS for path aggregation: When you need to compute values that depend on subtree results (like maximum path sums), use post-order traversal - process children first, then combine their results at the parent. This bottom-up approach ensures you have all necessary information before making decisions at each node.
• Dual-value return pattern: Distinguish between the value you return to parent (single-path sum for extension) versus the global answer you track (complete path sum). Return only the maximum single-branch path (node + max of left or right), but update global max with the full path (node + left + right) - this prevents invalid path shapes.
• Negative value handling with max(0, subtree): When dealing with potentially negative node values, use max(0, childSum) to decide whether to include a subtree. This elegantly handles the case where extending the path would decrease the sum - simply don't extend it. Never skip processing a node itself though, as it might be the best single-node path.
• Global variable for cross-subtree optimization: Use a global/nonlocal variable to track the maximum across all recursive calls, because the optimal path might not pass through the root and could span disconnected subtrees. The return value alone can't capture paths that branch in both directions at intermediate nodes.
• Path shape constraint awareness: Recognize that a valid path is linear or V-shaped (up to one turn), never Y-shaped. At each node, you can combine left subtree + node + right subtree for the global answer, but can only return node + one subtree upward, preventing the parent from creating an invalid multi-branched path.
• Single-node base case importance: Always consider that the optimal path might be a single node, especially with negative values. Initialize your global max to the first node's value or negative infinity, not zero, because an all-negative tree still needs to return its least negative node.