Binary Tree Maximum Path Sum: The Postorder Gain Pattern

Binary Tree Maximum Path Sum is the problem that separates people who use recursion from people who understand it. The prompt looks small, but it hides a genuinely tricky idea: the answer you report and the value you return to your parent are two different numbers, computed at the same node.

Get that distinction and the whole thing collapses into a ten-line postorder traversal. Miss it, and you'll write recursion that seems right and quietly returns the wrong answer on any tree with a branching optimum.

The pattern here — compute a gain to hand upward while separately tracking a global best — powers a whole family of tree problems: diameter, longest univalue path, house robber on trees. Learn it once.

The problem#

A path is any sequence of nodes connected by edges, where each node appears at most once. It does not have to pass through the root, and it does not have to touch a leaf. Given the root of a binary tree, return the maximum sum of node values along any such path.

The catch: a path can bend. It can go up from one leaf, through some ancestor, and back down into a different subtree. So the highest-value path might be left-child → parent → right-child, never continuing further up.

The answer is 15 + 20 + 7 = 42. The root -10 is poison — including it only drags the sum down — so the best path lives entirely inside the right subtree and ignores the root completely.

The brute force baseline#

The naive instinct is to enumerate paths: for every node, treat it as the topmost point of a path, then search downward for the best left arm and best right arm.

This is correct but wasteful. For each of the n nodes, visit calls maxArm, which re-walks that node's entire subtree. On a balanced tree that's O(n log n); on a degenerate spine it degrades to O(n²). Every downward arm gets recomputed from scratch, over and over.

The key insight: return the arm, record the bend#

Here is the reframe that makes the problem O(n). At every node you need two quantities, and they are not the same:

• The bend-through sum (currMax): node.val + bestLeftArm + bestRightArm. This is a valid answer candidate — a path that peaks at this node and dips into both children. But it can never be returned upward, because a parent extending through this node can only use one of its arms without the path forking.
• The return gain: node.val + max(bestLeftArm, bestRightArm). This is the strongest single downward arm. It's what the parent is allowed to attach to.

So each node computes the bend, offers it to a global maximum, and returns only the single-arm gain. Two more moves make it airtight:

1. Clamp negative arms to zero. Math.max(0, childGain) means a child that would only subtract from the sum contributes nothing — you simply don't walk into it.
2. Postorder. You need both children resolved before you can compute either quantity, so children are processed first, parent last.

The optimal solution#

This is the exact algorithm the visualizer traces, line for line:

Read the last three lines slowly, because they are the whole problem. currMax uses both arms and feeds the global answer. The return uses only the larger arm. maxSumPath starts at -Infinity, not 0, so an all-negative tree correctly reports its least-negative single node instead of a bogus 0.

Walkthrough#

Tracing [-10, 9, 20, null, null, 15, 7]. Postorder visits leaves first, so nodes complete in the order 9, 15, 7, 20, -10:

The decisive row is node 20: its bend-through sum 42 uses both children (15 and 7) and sets the global best. But it returns only 35 — the value of the single arm 20 → 15 — because that's all its parent can legally attach to.

At the root, -10 sees an incoming gain of 35 from the right, computes a bend of 34, and can't beat 42. Its own return value of 25 is discarded (nothing is above the root). The answer stays 42 — the path never touched the root at all.

Complexity#

Each node is touched exactly once and does constant work, so time is O(n) for n nodes. Space is O(h) where h is the tree height — the depth of the recursion stack. That's O(log n) on a balanced tree and O(n) on a fully skewed one.

Common mistakes#

• Returning currMax instead of the single arm. If you return node.val + maxLeft + maxRight, the parent inherits a forked path — a shape that isn't a valid path anymore. Return node.val + max(maxLeft, maxRight).
• Initializing the answer to 0. For a tree like [-3] or [-1, -2, -3], a 0 start reports 0, but no empty path is allowed — the answer must be the least-negative single node. Start maxSumPath at -Infinity.
• Forgetting to clamp negative arms. Without Math.max(0, ...), a strongly negative subtree gets forced into the sum. The clamp says "if this arm hurts, take nothing from it."
• Comparing at the wrong moment. You must fold currMax into the global best at every node, not only at the root. The optimal bend can peak deep inside a subtree — as it does at node 20 above.
• Confusing the two return points. maxSumPath is the reported answer; the function's return is plumbing for the parent. They are computed side by side and mean different things.

Where this pattern shows up next#

The "return a gain, record a global best in postorder" template is the backbone of tree DP. Once the bend-vs-return split clicks here, these traversals feel like variations on one theme:

• Binary Tree Preorder Traversal — the root-first ordering, the mirror of the postorder we lean on here.
• Binary Tree Inorder Traversal — left-root-right, the ordering that sorts a BST.
• Binary Tree Preorder Traversal - Iterative — the same order with an explicit stack instead of the call stack.
• Binary Tree Inorder Traversal - Iterative — how to unwind recursion into a manual stack, which is exactly the O(h) frame our solution uses implicitly.

You can also step through Binary Tree Maximum Path Sum interactively to watch the call stack build up, the arms clamp, and the global best jump the moment node 20's bend fires.

FAQ#

Why does the function return a different value than the answer it records?#

Because a path that bends through a node cannot be extended past it without forking. The bend-through sum (node.val + maxLeft + maxRight) is a complete path that peaks at the current node, so it's a valid answer candidate and gets compared against the global maximum. But the value handed to the parent is node.val + max(maxLeft, maxRight) — only the stronger single arm — because the parent needs a straight line it can attach to, not a fork. Recording one number and returning the other, at the same node, is the entire trick.

Why clamp the child gains with Math.max(0, ...)?#

A subtree can return a negative gain when all its downward paths lose value. Including such an arm only shrinks your sum, so you should simply not walk into it. Math.max(0, traversal(child)) replaces any negative contribution with zero, which is equivalent to choosing an empty arm on that side. Without the clamp, a deeply negative subtree would be forced into every parent's calculation and corrupt the answer.

Why initialize maxSumPath to -Infinity instead of 0?#

Because a valid path must contain at least one node — the empty path is not allowed. If every value in the tree is negative, the best path is the single least-negative node. Starting at 0 would wrongly report 0 (as if you could pick nothing), while starting at -Infinity guarantees the first real node's value overwrites it. For [-1, -2, -3] the correct answer is -1, and only the -Infinity start produces it.

What is the time and space complexity?#

Time is O(n) for a tree of n nodes: each node is visited exactly once and does constant work — two child calls, a couple of max operations, one comparison. Space is O(h) where h is the height of the tree, driven entirely by the recursion call stack. That's O(log n) for a balanced tree and O(n) in the worst case of a completely unbalanced spine.

Does the maximum path have to include the root or reach a leaf?#

No to both. A path is any connected chain of distinct nodes, and it can start and end anywhere. It might live entirely inside a subtree and never touch the root — as in the worked example, where the root -10 is skipped and the answer 42 comes from 15 → 20 → 7. It can also stop mid-tree without descending to a leaf. That freedom is exactly why every node has to be considered as a potential bend point.