Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum is a classic recursion problem. It looks scary because a path can wander anywhere in the tree, but one clean DFS idea tames it: at each node, separate "the best arm I can pass upward" from "the best path that bends right here."

The slow way first

The brute idea is to enumerate every possible path and sum it. But paths can start and end at any pair of nodes and bend at a turning point, so there are far too many of them — this blows up well past polynomial time. We need to reuse work as we walk the tree, not restart from scratch for every path.

The question to ask: as DFS leaves a node, what single number summarizes everything below it that the parent could use?

The idea: arms going up, bends staying put

For each node, DFS computes two things from its children:

• The arm it returns upward. A path that continues into the parent may use only one child arm (it cannot branch). So a node returns node.val + max(leftArm, rightArm).
• The bent path that turns here. A path is allowed to come up the left arm, pass through this node, and go down the right arm: node.val + leftArm + rightArm. That path cannot extend upward, so we just compare it against a running global best.

Negative arms are never worth keeping, so each arm is clamped with max(0, childArm).

The key insight: the two-armed bent sum is only ever a candidate for the answer, never a return value, because a bent path has used up both of its directions.

Walk through it

Step through the animation. DFS dives to the leaves first. Each leaf has arms 0, 0, so it returns its own value. At node 20, both arms are positive (15 and 7), so the bent path 20 + 15 + 7 = 42 updates the global best — but 20 only returns 20 + max(15, 7) = 35 to its parent. At the root -10, the bent path is -10 + 9 + 35 = 34, which loses to 42, so the answer stays 42.

Pseudocode

best = -infinity
define dfs(node):
    if node is empty: return 0
    leftArm  = max(0, dfs(node.left))    # drop negative arms
    rightArm = max(0, dfs(node.right))
    bent = node.val + leftArm + rightArm  # path that turns here
    best = max(best, bent)                # candidate for the answer
    return node.val + max(leftArm, rightArm)   # single arm goes up
run dfs(root)
return best

The Python solution

def max_path_sum(root):
    best = float('-inf')
    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return best

• best lives outside dfs and is updated through nonlocal, because the answer can turn at any node anywhere in the tree.
• An empty child returns 0, which is also the identity for the max(0, ...) clamp.
• left and right are each clamped at 0 — a negative arm is dropped because skipping it is never worse.
• Line 9 scores the bent path node.val + left + right and feeds it to the global best. This is the only place the answer is recorded.
• Line 10 returns just node.val + max(left, right) — a single arm — because a path going up to the parent cannot branch.

Complexity

We touch every node exactly once, so time is O(n). The extra space is the recursion stack, O(h) where h is the tree height — O(log n) for a balanced tree, O(n) in the worst case.

When this pattern shows up

Practice