Binary Tree Maximum Path Sum

The trap is subtle: one path can use both child branches at its turning point, but only one of those branches can continue upward to a parent. Keep those two jobs separate.

Enumerate every path

A tree has exactly one route between any two nodes. Treat each edge as two-way, record every node's parent, then choose every possible starting node and walk to every reachable endpoint. The running total on each walk is one candidate path sum.

def max_path_sum(root: TreeNode) -> int:
    nodes: list[TreeNode] = []
    parent: dict[TreeNode, TreeNode | None] = {root: None}
    stack = [root]
 
    while stack:
        node = stack.pop()
        nodes.append(node)
        if node.left is not None:
            parent[node.left] = node
            stack.append(node.left)
        if node.right is not None:
            parent[node.right] = node
            stack.append(node.right)
 
    best = root.val
    for start in nodes:
        paths = [(start, None, start.val)]
        while paths:
            node, previous, total = paths.pop()
            best = max(best, total)
            for neighbor in (node.left, node.right, parent[node]):
                if neighbor is not None and neighbor is not previous:
                    paths.append((neighbor, node, total + neighbor.val))
 
    return best

Time O(n²) — each of n starting nodes can visit all n nodes. Space O(n) for the parent map, node list, and traversal stack.

Post-order gains

A post-order traversal processes both children before their parent. That timing lets each child report a downward arm — the best path that starts at that child and follows at most one child branch.

At node, clamp each child's arm to zero because extending through a negative total can only hurt. Two different calculations now matter:

• node.val + left_gain + right_gain is the best complete path whose turning point is node. It may bend through both children, so use it to update the global answer.
• node.val + max(left_gain, right_gain) is the one arm the parent may extend. Clamp that result to zero before returning it.

import sys
 
 
def max_path_sum(root: TreeNode) -> int:
    sys.setrecursionlimit(20_000)
    best = root.val
 
    def best_arm(node: TreeNode | None) -> int:
        nonlocal best
        if node is None:
            return 0
 
        left_gain = best_arm(node.left)
        right_gain = best_arm(node.right)
 
        best = max(best, node.val + left_gain + right_gain)
        return max(0, node.val + max(left_gain, right_gain))
 
    best_arm(root)
    return best

Why does this cover every answer? Take any path and find its highest node in the rooted tree. The path uses at most one downward arm from each child of that node, exactly the candidate the traversal evaluates there. Since every node gets that chance, the best candidate can't be missed.

Initialize best from a real node, not zero. Returned arms may discard a loss, but the final path may never be empty; a tree full of negative values must return its least negative node.

Time O(n) — every node is processed once. Space O(h) for the recursion stack, where h is the tree height; the raised recursion limit covers the allowed skewed case.