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
   15    7

To put this in plain English: you can start at any node in the tree and follow the branches down (and optionally up through parents and then down another side) to any other node, tracing a single continuous path. You want to find the path that gives you the highest possible sum when you add up all the numbers along it.

Constraints to Keep in Mind:

• 1 <= Number of nodes in the tree <= 3 * 10^4
• -1000 <= Node.val <= 1000
• Values may be negative.

The Brute Force Approach

A naive approach would be to calculate the path sum for every single possible path in the tree.

• How it works: For each node A, you could run a DFS to find paths from A down to every other node B in its left and right subtrees. You'd sum these up and find the max.
• Why it's too slow: Finding paths between all possible pairs of nodes would take O(n^2) or O(n^3) time, depending on implementation. In a tree with 30,000 nodes, this is extremely inefficient. We need an approach that only visits each node once in O(n) time.

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;
}

Code Walkthrough

1. self.best = float('-inf'): Initialize our global max tracker. It must be negative infinity so that if the whole tree is negative, the highest negative number can still win.
2. def gain(node) -> int:: Our recursive helper. It returns the maximum path sum starting at node and going straight down ONE side.
3. if not node: return 0: Base case. An empty tree contributes a sum of 0.
4. left = max(gain(node.left), 0): Find the max sum we can get by going into the left subtree. If that sum is negative, we clamp it to 0 (meaning we just don't go left at all).
5. right = max(gain(node.right), 0): Do the same for the right subtree.
6. self.best = max(self.best, node.val + left + right): Calculate the maximum path that turns AT this node. It includes the node's own value plus the BEST we can get from BOTH sides (since left and right are already clamped to 0 if they hurt). We record this if it's a new high score.
7. return node.val + max(left, right): This is what we pass UP to the parent. The parent can't turn at this node if it's already a continuous path from above, so the path can only continue down one side (whichever is bigger).

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

• Time Complexity: O(n). We do a post-order traversal, visiting each of the n nodes exactly once. At each node, we do O(1) constant time additions and max operations. Thus, time is directly proportional to the number of nodes.
• Space Complexity: O(h). The only extra memory is the call stack for the recursive DFS. This is equal to the height of the tree h, which is O(\log n) for a balanced tree and O(n) for a completely unbalanced tree.

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.