Binary Tree Maximum Path Sum

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

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

Solution

Approach: DFS with Path Sum Tracking

The key insight is that for each node, the maximum path through it is: node.val + max_left_gain + max_right_gain. We track the global maximum while computing the maximum gain from each subtree.

Implementation

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')

        def max_gain(node):
            if not node:
                return 0

            # Recursively get max gain from left and right subtrees
            # Use max with 0 to ignore negative paths
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            # Price of path through current node
            path_sum = node.val + left_gain + right_gain

            # Update global maximum
            self.max_sum = max(self.max_sum, path_sum)

            # Return max gain if continuing from this node to parent
            # Can only choose one path (left or right), not both
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return self.max_sum

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Key Insights

Two Types of Paths: A node can be (1) the “turning point” where path goes through it to both children, or (2) part of a path going to parent.
Gain vs Path Sum: For a node, we compute two values: the maximum path sum through it (for global max), and the maximum gain contributing upward (for parent’s calculation).
Ignore Negative Paths: Using max(gain, 0) means we don’t include a subtree if it has negative sum.
Can Only Choose One Child: When returning gain to parent, we choose max of left or right, not both, since a path can’t split.
Global Maximum: The answer might be anywhere in the tree, not necessarily passing through root, so we track a global maximum.