Binary Tree Maximum Path Sum: The Hard Version of Diameter

If you interview at Meta, Amazon, Google, expect some version of "Binary Tree Maximum Path Sum". It is rated Hard, and it falls squarely into the Tree DFS pattern — pattern-first preparation beats grinding random problems every time. Part 11 of 11 in the Tree DFS arc.

The Problem

A path is any node sequence connected by edges, appearing at most once each, no root requirement. Return the maximum sum over all paths of at least one node. Values can be negative — which is what promotes Diameter's shape into a hard problem.

Input:  root = [-10, 9, 20, None, None, 15, 7]
Output: 42
The path 15 -> 20 -> 7. For root = [-3] the answer is -3.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

Same two-quantity shape as Diameter: the value extendable upward (node plus its better arm) differs from the local candidate (node plus both arms). Negativity adds the clamp — an arm that sums negative is worth zero, i.e., excluded — and the all-negative case forbids initializing the best at zero.

The Approach

Post-order helper gain(node): the best downward path starting at node, clamped at zero via max(gain, 0) on each child. At each node, update the global best with node.val + left_gain + right_gain — the path bending here. Return node.val + max(left_gain, right_gain) upward.

Initialize the best to negative infinity so a tree of all negatives returns its largest single node. The clamp and the initialization are the two marks between a pass and a fail on this question.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def max_path_sum(root: TreeNode) -> int:
    """Maximum sum over all any-to-any paths."""
    best = float("-inf")

    def gain(node: TreeNode | None) -> int:
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)     # negative arms are dropped
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return int(best)

Complexity

• Time: O(n) — one post-order pass
• Space: O(h) — recursion stack

Interview Tips and Follow-Ups

• Walk the all-negative tree aloud ([-2, -1] returning -1) — it simultaneously tests the clamp and the initialization, and interviewers reach for it first.
• Contrast with Diameter explicitly: same skeleton, plus value weights, plus the zero-clamp. Presenting it as an upgrade shows the pattern lens working.
• Returning the actual path (not just the sum) requires tracking the argmax structure through the recursion — sketch how before it is asked.

If this clicked, continue the Tree DFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.