Problem 29 · Trees

Binary Tree Maximum Path Sum

HardClassic DSA & systems

01Problem

A path is any sequence of connected nodes with no node repeated; return the maximum sum over all non-empty paths.

02Key insight

Each node returns the best downward 'gain' (clamped at 0) to its parent, while separately updating a global best with node + left gain + right gain, the path that bends at this node.

03Solution

solution.pypython21 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def max_path_sum(root: TreeNode) -> int:
    best = root.val
    def gain(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        left, right = max(gain(node.left), 0), max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    gain(root)
    return best

Try it first.

TimeO(n)

SpaceO(h)

tests.py · 4 passing

tests.pypython5 lines

T = TreeNode
assert max_path_sum(T(1, T(2), T(3))) == 6
assert max_path_sum(T(-10, T(9), T(20, T(15), T(7)))) == 42
assert max_path_sum(T(-3)) == -3
assert max_path_sum(T(-2, T(-1))) == -1

04Staff-level follow-up

Tree depth may be 10^5? Recursion overflows Python's stack; convert to an iterative post-order that stores each node's gain in a dict.