Binary Tree Maximum Path Sum

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

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can not appear in the sequence more than once. The path does not necessarily need to include the root.

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

The path is 2 -> 1 -> 3 with a sum of 2 + 1 + 3 = 6.

The path is 15 -> 20 -> 5 with a sum of 15 + 20 + 5 = 40.

Approach

Use DFS to compute the maximum gain from each node to its parent. For a node, the best gain is its value plus the maximum of the left or right gain (ignoring negative gains). Track a global maximum for paths that pass through the node using both left and right gains. This handles all-negative trees by allowing single-node paths.

Why It Works

Any maximum path either passes through a node (using left and right branches) or lies entirely in one subtree. The DFS computes the best downward gain to extend a path upward, while the global maximum considers the best "through-node" path. Taking the max across all nodes yields the correct answer.

Complexity

• Time: O(n)
• Space: O(h)

Reference Implementation (Python)

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

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal best
            if not node:
                return 0
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)
            best = max(best, node.val + left_gain + right_gain)
            return node.val + max(left_gain, right_gain)

        dfs(root)
        return best