Canonical Deep-Dive: Binary Tree Maximum Path Sum

Problem: Binary Tree Maximum Path Sum (https://leetcode.com/problems/binary-tree-maximum-path-sum/) The lesson: the return-versus-record split, the idea that one recursive call must hand its parent one quantity while saving a different quantity off to the side.

This is a guided walk-through, not an answer key. It explains how to think about the split between what a recursion returns and what it records, shows you the two expressions as relations, and names the base case and the complexity in words. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given the root of a binary tree. A path is any sequence of nodes where each consecutive pair is connected by an edge, and no node is used twice. A path does not have to pass through the root, and it does not have to touch a leaf; a single node by itself is a valid path. The path sum is the total of the node values along the path. Return the maximum path sum over every possible path in the tree. Node values can be negative, which is the whole difficulty.

Why this is not just “sum the tree”

If every value were non-negative, you would take the whole tree and be done. Negative values break that: sometimes the best path is a single node, sometimes it skips an entire negative subtree, and sometimes it bends through an interior node and never comes near the root. Consider the tree [-10, 9, 20, null, null, 15, 7]: a root of -10 with children 9 and 20, and 20 in turn has children 15 and 7. The best path is 15 -> 20 -> 7, summing to 42. It never touches the root, and it bends: it comes up from 15, turns at 20, and goes back down to 7. Any approach that only ever reports values upward to the root will miss it.

That bend is the crux. A path is a line through the tree; at the node where it turns, it uses both of that node’s downward directions at once. But the moment you hand a result up to a parent, the parent can only continue the line in one direction (down toward the parent’s other side, or up again). So a node faces two genuinely different questions, and you must answer both.

The two questions every node answers

Stand at a node and ask:

“If my parent wants to build a path that comes down through me and keeps going, how much can I contribute?” This is a straight line down: my value, plus the best single downward direction (left or right, whichever is larger), but never both, because the parent is going to extend through me and a line cannot fork. And if a side’s best contribution is negative, I refuse it and contribute 0 from that side instead (better to stop than to drag the total down). This is the quantity I return to my parent.
“What is the best path whose highest point (its bend) is me?” This is my value, plus whatever each side can contribute on its own (again, refusing any negative side by treating it as 0), taking both sides at once. This is a complete path; it does not go anywhere after me. It cannot be returned, because my parent can only use one side of me. So I record it: compare it against the best-so-far and keep the larger.

The first answer is what flows up the recursion. The second answer is the candidate for the final result. They are computed from the same two child values, but they combine them differently (one side versus both sides), and they have different fates (returned versus recorded). That is the return-versus-record split, in full.

The split, as two relations

Let left be the gain returned by the left child and right the gain returned by the right child. Clamp each to be at least zero, because a negative gain is one you decline:

left_gain  = max(0, gain(node.left))
right_gain = max(0, gain(node.right))

Then the two quantities are:

RETURN to the parent:   node.val + max(left_gain, right_gain)
RECORD into best:       best = max(best, node.val + left_gain + right_gain)

The returned value uses max(left_gain, right_gain), a single side, because the parent will extend the line through this node and cannot use both. The recorded value uses left_gain + right_gain, both sides, because that bent path ends here and is a complete candidate answer. Read those two lines until the difference (one side versus both) is obvious; that difference is the entire lesson.

What gets recorded, and why it starts at negative infinity

The “best so far” is not a return value; it is a single quantity that has to survive across every call of the recursion, because the winning path can be discovered deep in any subtree. The Python idiom for that is a nonlocal variable in an enclosing function (refresher section 10): the inner helper returns the straight-line gain to its caller, and along the way it writes the best bent path it has seen into the enclosing best. (A class attribute, self.best, does the same job; use whichever you find clearer.)

Seed best at float('-inf'), not 0. If you start it at 0, you silently assume the answer is at least zero, which is wrong when every node is negative: for a tree that is a single node -3, the only path is that node and the answer is -3. Starting at negative infinity lets the first node the recursion records overwrite it, so an all-negative tree reports its least-bad single node correctly. This is exactly the “use float('-inf') as smaller than any real value” idiom from the refresher, applied to a maximum instead of a minimum.

The base case

The base case is node is None, the empty subtree, and an empty subtree contributes a gain of 0. That is why the clamp max(0, ...) and the None base case fit together: a missing child returns 0, which the clamp would have produced anyway, so leaves need no special handling. A leaf is simply a node whose two recursive calls both hit the None base case and return 0, leaving its returned gain as node.val and its recorded candidate as node.val as well. Do not try to detect leaves; recurse into None and let 0 do the work.

The order is post-order, and that is not a coincidence

You cannot compute either quantity at a node until you know both children’s gains, so you must visit the children before the node. That is post-order (left, right, then node), the traversal whose defining feature is that a node is processed only after its subtrees. Every “the node’s answer is built from its children’s answers” tree problem is post-order for this reason; recognizing that saves you from reaching for the wrong traversal.

The key insight, in one sentence

At each node, return to your parent the best straight line going down (your value plus the better one of your two children’s non-negative gains), but record into a running best the best bend (your value plus both children’s non-negative gains), because the line is what a parent can extend and the bend is a finished path that can only end at you. Compute it post-order, seed the best at negative infinity so an all-negative tree still has an answer, and the running best at the end is the result.

Exact complexity

Time: O(n), where n is the number of nodes. Each node is visited exactly once, and does a constant amount of work (two max calls, two additions, one comparison). There is no revisiting and no hidden factor.
Space: O(h), where h is the height of the tree, for the recursion call stack (the deepest the recursion goes before unwinding). For a balanced tree that is O(log n); for a skewed tree it degrades to O(n), which is the case to mention in an interview and the shape that could hit the recursion-depth limit. You store only the single best besides the stack, so the stack dominates.

State both clearly: O(n) time because every node is touched once, O(h) space because the recursion stack is as deep as the tree is tall, and h ranges from log n (balanced) to n (skewed).

Your work this week

Implement Binary Tree Maximum Path Sum yourself, in your own work repo (for example binary-tree-maximum-path-sum.py). Write the recursive helper that returns the straight-line gain and records the bent path into a nonlocal best (or self.best). Seed best at float('-inf'). Build it from the two relations above; do not copy a solution.
Before you write code, write the two sentences in plain English: “this call RETURNS __” and “this call RECORDS __, because a bent path cannot be returned.” If you cannot write both, re-read the two-questions section; that is the understanding the problem is testing.
Test the edge cases yourself: a single node (the answer is that node’s value, including when it is negative), an all-negative tree (the answer is the least-negative single node, which is why best cannot start at 0), [1, 2, 3] (answer 6, the whole tree), and [-10, 9, 20, null, null, 15, 7] (answer 42, a bend below the root). Then submit to LeetCode’s judge.
Commit with a five-question debrief in the message. In answer 3, state the exact complexity above (O(n) time, O(h) space) and explain, in one sentence each, what the recursion returns and what it records and why those differ.

When you can explain, from memory and with no AI open, what the recursion returns versus what it records, why the recorded bend uses both sides while the returned line uses one, and why best starts at negative infinity, you own this problem. That explanation is exactly what an interviewer will ask for, and the return-versus-record split is the template you will reuse on a whole family of tree problems.