4.14.14 — Binary Tree Maximum Path Sum

LeetCode 124 · Hard · ★ Blind 75

The problem

A path is any sequence of connected nodes, where each pair of neighbours shares an edge, and no node appears twice. The path does not have to pass through the root. Return the largest possible sum of node values along a path.

   1
  / \        →  6      (2 + 1 + 3)
 2   3

  -10
  /  \
 9    20     →  42     (15 + 20 + 7 — the root is not used)
     /  \
   15    7

Values may be negative.

The pattern

This is 4.14.3 Diameter with sums instead of lengths, plus one new complication.

Every path has a highest node, where it turns around. For a path turning at node X:

\text{sum} = X.val + \text{best downward sum from left} + \text{best downward sum from right}

So try every node as the turning point.

And the same two-value split applies:

• Return upwards: the best sum of a path that starts at this node and goes straight down one side. A parent can only continue through one child.
• Record on the side: the best sum turning here, using both children. That path cannot continue upwards, so it is never returned.

What negative numbers change

This is the difference from Diameter, and it is the whole difficulty.

A subtree may return a negative sum. Attaching it makes the path worse. So the right move is not to attach it at all.

left = max(dfs(node.left), 0)      # if it hurts, contribute nothing

max(..., 0) means "take this branch, or take nothing". Taking nothing is always available because a path can simply start at the current node.

This one line is the difference between a correct solution and a wrong one, and it is what makes the second example work: the root -10 is skipped entirely, and the best path lives inside the right subtree.

Do not apply the same clamp to the answer being recorded. Every node must be allowed to be a path on its own, so on an all-negative tree the answer is the single least-negative value. Clamping the recorded value to 0 would return 0 for a tree with no non-negative nodes, which is wrong.

The solution

Python

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

        def gain(node) -> int:
            if not node:
                return 0

            left = max(gain(node.left), 0)         # drop a harmful branch
            right = max(gain(node.right), 0)

            self.best = max(self.best, node.val + left + right)   # turn here

            return node.val + max(left, right)     # continue upward, one side only

        gain(root)
        return self.best

TypeScript

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;

  function gain(node: TreeNode | null): number {
    if (!node) return 0;

    const left = Math.max(gain(node.left), 0);
    const right = Math.max(gain(node.right), 0);

    best = Math.max(best, node.val + left + right);

    return node.val + Math.max(left, right);
  }

  gain(root);
  return best;
}

Four lines, four reasons.

max(gain(...), 0) — a negative branch contributes nothing.

node.val + left + right — the candidate answer, using both sides. Recorded, never returned.

node.val + max(left, right) — what goes to the parent. Only one side, because a path through this node and onwards to the parent cannot also go down the other side without visiting this node twice.

best starts at negative infinity, not 0, so an all-negative tree gives the correct answer.

Trace

  -10
  /  \
 9    20
     /  \
   15    7

node	left gain	right gain	candidate recorded	returns
9	0	0	9	9
15	0	0	15	15
7	0	0	15 → stays	7
20	15	7	42	20 + 15 = 35
−10	9	35	−10 + 9 + 35 = 34	—

Best is 42, recorded at node 20. The root's own candidate of 34 loses, which is exactly the point — the answer does not pass through the root.

Complexity

O(n) time, O(h) space.

Where this goes next

• Diameter of Binary Tree — the same structure counting edges. 4.14.3.
• Longest ZigZag Path — return two values, one per direction.
• House Robber III — return two values, "best if I take this node" and "best if I skip it". The same shape with a richer return type, and it is DP on a tree.
• Path Sum III — count paths with a given sum, using prefix sums along the root-to-node path with a hash map. That is 4.4.3 Two Sum's look-back move applied to a tree.

The rule: return what the parent can use; record what the question wants; and where a contribution can hurt, clamp it to zero.

What the interviewer will push on

"Why does the function return something different from the answer?" A parent can only extend one side, so it needs the one-sided sum. The answer uses both sides and cannot continue upward.

"What do negative values change?" max(gain, 0) — dropping a branch that hurts.

"Why does best start at negative infinity?" An all-negative tree. If it started at 0 you would return 0 for [-3].

"Why not clamp the recorded candidate too?" Same reason — a single negative node must remain a legal path.

"Can a path go down, up, and down again more than once?" No. Each node appears once, so a path turns at exactly one node. That is why trying every node as the turning point covers every path.

One thing to volunteer: say the two-value split before writing anything, then say what negatives change. Those two sentences are the whole solution, and stating them first is far more convincing than producing the code and hoping it is right.

Next: 4.14.15 Serialize and Deserialize Binary Tree — turning a tree into a string and back, which closes the chapter.