Binary Tree Maximum Path Sum — The Gold Vein

Boss 14: The Gold Vein

The summit. LeetCode Hard, a fixture of final-round interviews, and, if Bosses 3 and 10 landed, about four lines of new thinking. That's not a humblebrag on the dungeon's behalf: Maximum Path Sum is the diameter problem with money, and the entire difficulty lives in one question the diameter never had to ask: what if a branch is worth less than nothing?

The story

The company inherits a mapped tunnel network. Each chamber's survey value: positive for ore, negative where flood damage makes traversal a net loss.

        -10
        /  \
       9    20
           /  \
         15    7

They'll cut one continuous path, start anywhere, end anywhere, no revisiting, and a path may bend through a chamber (up one branch, down the other), same geometry as the zipline in Boss 3. Maximize the total survey value along the path.

Candidates: the path holding 9 alone is worth 9. The path 15 → 20 → 7 bends at 20: 15 + 20 + 7 = 42. Extending it up through -10 to reach 9? That's 42 - 10 + 9 = 41. Worse. The best path refuses the root, the -10 chamber is a toll not worth paying even to connect two profitable regions.

And sharpen the edge case now: a mine where every chamber is negative, say all values -3. The best path is a single chamber, total -3. "Take nothing" isn't an option, a path has at least one chamber, and this detail decides where initializations and clamps go.

The problem, dressed up properly

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

LeetCode 124. Values range down to -1000, and "non-empty" is the all-negative clause in contract language.

The naive attempt

Enumerate paths? The number of paths in a tree is quadratic (every pair of nodes defines one), and summing each costs more; O(n²) at best with cleverness, and structurally messy to even enumerate. The honest naive framing is Boss 3's: for every chamber, the best path bending there is (best downward arm on the left) + (chamber) + (best downward arm on the right), computed with a fresh depth-style scan per chamber, O(n²).

You already know the cure for the re-scanning. What Boss 3 didn't have: arms that can be liabilities.

The weapon: two channels, one clamp

The Boss 3 architecture, verbatim: each chamber returns its best extendable arm upward and logs its best bend into a side channel. Now the money twist, and the four lines of new thinking:

An arm's value can be negative, and a negative arm is never worth attaching. If the best arm below-left sums to -7, the bend at this chamber does better by ignoring the left entirely, a bend doesn't have to use both sides, or either. The fix is a clamp:

left_arm  = max(0, best_arm(left))
right_arm = max(0, best_arm(right))

Read max(0, ...) as a business decision: an arm worth less than nothing is replaced by no arm at all. Zero is the value of not digging.

With clamped arms, everything else is Boss 3:

• Log the bend: left_arm + node.val + right_arm. (With clamps, this single expression covers node-alone, node-plus-one-arm, and node-plus-both, whichever is best, the clamp already zeroed the losers.)
• Return the arm: node.val + max(left_arm, right_arm). An arm extends through one side only, and note the node's own value is not clamped here, a parent extending down to this chamber must pay its toll; refusing the chamber is the parent's decision, made by its clamp.

Why must best be seeded with negative infinity and not zero? The all-negative mine. Every bend there sums negative, and a zero seed would "win" with a path that doesn't exist. The side channel's seed encodes "non-empty path required"; the clamp encodes "sides are optional". Two different zeros, two different jobs, keeping them straight is this boss.

Watching it work

arm(9):   arms 0,0 → log 9,  return 9
arm(15):  log 15, return 15
arm(7):   log 7,  return 7
arm(20):  left_arm 15, right_arm 7
          log 15+20+7 = 42   ← the vein
          return 20 + max(15,7) = 35
arm(-10): left_arm max(0,9)=9, right_arm max(0,35)=35
          log 9 + (-10) + 35 = 34
          return -10 + 35 = 25 (nobody above to care)

best: max(9, 15, 7, 42, 34) = 42 ✓

The root's own bend (34) dutifully considered, dutifully beaten. The mine's answer formed at chamber 20 and no ancestor could improve it, exactly the "answer lives anywhere" lesson from Boss 3, now with the root actively hurting any path through it.

The code

def max_path_sum(root: TreeNode) -> int:
    best = float("-inf")                 # non-empty path: seed below any real sum
 
    def arm(node):
        nonlocal best
        if not node:
            return 0
        left_arm = max(0, arm(node.left))     # a losing arm is no arm
        right_arm = max(0, arm(node.right))
        best = max(best, left_arm + node.val + right_arm)   # bend here
        return node.val + max(left_arm, right_arm)          # extend one side up
 
    arm(root)
    return best

Nine lines for a Hard. Every line is a boss you've already beaten: the post-order shape (Boss 2), the two channels (Boss 3), the side-channel state (Boss 3), the downward-free clamp reasoning standing in for a sentinel (Boss 4's cousin), the seed discipline (Boss 10's -inf).

Gotchas

1. Returning the bend. Boss 3's cardinal sin, worth restating with money: a bend used both sides, so the parent can't extend it, a path can't have three ends. Return the one-sided arm, log the bend.

2. Seeding best with 0. All-negative mine returns 0, claiming a profitable path exists in a mine that only loses money. The answer there is the least-bad single chamber. -inf seed, non-negotiable.

3. Clamping the return. The phantom-free-tunnels bug from the callout. Clamp received arms, never your own report.

4. Forgetting the node-alone case. Covered automatically: both arms clamp to 0 and the bend log becomes 0 + val + 0. If your version enumerates cases (val, val+left, val+right, val+both) instead of clamping, it can be correct but it's four expressions doing one clamp's work, and interviewers notice the difference.

5. Global state across test cases. best as a class attribute survives between LeetCode calls and haunts the second test. Keep it function-local (nonlocal) or reset it explicitly. This bug has ended otherwise-perfect interviews.

Complexity

One post-order pass, constant work per chamber.

Time: O(n). Space: O(h) stack.

Boss down. XP gained. The summit is yours.

The cutter follows 15 → 20 → 7, the flooded -10 chamber stays sealed forever, and the survey team's nine-line memo becomes company legend.

What you walked away with:

• Max Path Sum = diameter + money + one clamp: max(0, arm) turns "negative branch" into "no branch"
• Two zeros, two jobs: clamp-zero means "sides are optional", -inf seed means "the path is not"
• Truth flows up unclamped; the receiver decides refusal
• Hard problems as compositions: every line of this boss was a previous boss's lesson

One boss remains. After fourteen rounds of holding trees in memory, the finale asks you to flatten one into a string and resurrect it, the skill that lets trees cross networks, hit disks, and survive process death. The dungeon's most shippable lesson.

Next up: Boss 15 — The Bonsai Courier. A prize bonsai must ship across the country flat-packed: written down as a single line of text, then regrown at the destination, identical, empty branches and all. Boss 13 said one traversal can't determine a tree, unless it records the Nones. Time to cash that loophole.