Binary Tree Maximum Path Sum: Post-Order Gains with a Global Best

Problem

A path in a binary tree is a sequence of distinct nodes where each consecutive pair is joined by an edge. It contains at least one node, need not pass through the root, and can go up from one node and back down into another branch, but never visits a node twice. Given the root of a non-empty tree whose values may be negative, return the largest possible sum of values along any path.

This is widely known as LeetCode 124 (Binary Tree Maximum Path Sum). It is a frequently asked hard tree problem, and it is the diameter pattern with weights.

Constraints for this version: 1 to 30,000 nodes; values between -1,000 and 1,000.

Examples

Tree (level order)	Best sum	Best path
[2, -1, 3]	5	2, 3 (dropping -1 helps)
[-8, 6, 15, None, None, 4, 9]	28	4, 15, 9 (does not use the root)
[-3]	-3	the only node
[-2, -5, -1]	-1	single node -1; every other path is worse

Approach 1: brute force

Every path is determined by its two end nodes. Treat the tree as an undirected graph, run a depth-first search from every node and track the best running sum to every reachable node.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum_brute(root):
    # build an undirected adjacency list
    neighbours, stack = {}, [root]
    while stack:
        node = stack.pop()
        neighbours.setdefault(node, [])
        for child in (node.left, node.right):
            if child:
                neighbours[node].append(child)
                neighbours.setdefault(child, []).append(node)
                stack.append(child)
    best = float("-inf")
    for start in neighbours:                    # every path starting at `start`
        frontier = [(start, None, start.val)]
        while frontier:
            node, parent, total = frontier.pop()
            best = max(best, total)
            for nxt in neighbours[node]:
                if nxt is not parent:
                    frontier.append((nxt, node, total + nxt.val))
    return best

O(n^2) time, because there are about n^2 / 2 paths in a tree. Useful as a reference to test the fast version against.

Approach 2: optimal

Key insight. Look at each path from its highest node. At that node the path takes the best downward chain from the left (or nothing), the node itself, and the best downward chain from the right (or nothing). So for every node you need one number from each child: the best downward gain, the largest sum of a path that starts at the child and goes down. A negative gain is never worth taking, so clamp it to 0.

Two different values per node, which is the crux:

• Path bending here (candidate answer): node.val + left_gain + right_gain.
• Gain returned to the parent: node.val + max(left_gain, right_gain). A path that continues upward cannot use both branches, or it would visit this node twice.

Walkthrough for [-8, 6, 15, None, None, 4, 9]:

Node	Left gain	Right gain	Path bending here	Returns
6	0	0	6	6
4	0	0	4	4
9	0	0	9	9
15	4	9	28	24
-8	6	24	22	16

The best is 28, at node 15.

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)          # drop negative branches
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

Iterative post-order version, safe for deep trees:

def max_path_sum_iterative(root):
    best = float("-inf")
    gains = {None: 0}
    stack = [(root, False)]
    while stack:
        node, ready = stack.pop()
        if ready:
            left = max(gains[node.left], 0)
            right = max(gains[node.right], 0)
            best = max(best, node.val + left + right)
            gains[node] = node.val + max(left, right)
        else:
            stack.append((node, True))
            for child in (node.right, node.left):
                if child:
                    stack.append((child, False))
    return best

Complexity. O(n) time. O(h) recursion depth, or O(n) for the dictionary in the iterative version.

Tests

from collections import deque
import random

def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

cases = [
    ([2, -1, 3], 5),
    ([-8, 6, 15, None, None, 4, 9], 28),
    ([-3], -3),
    ([-2, -5, -1], -1),
    ([1, 2, None, 3, None, 4], 10),              # skewed: whole chain
    ([5, 5, 5, 5, 5, 5, 5], 25),                 # duplicates: 5+5+5+5+5 through the root
    ([10, -20, -20, 30, None, None, 40], 40),
]
for fn in (max_path_sum_brute, max_path_sum, max_path_sum_iterative):
    for values, want in cases:
        assert fn(build_tree(values)) == want, (fn.__name__, values)

rng = random.Random(21)
for _ in range(300):
    values = [rng.randint(-10, 10) for _ in range(rng.randint(1, 15))]
    tree = build_tree(values)
    assert max_path_sum(tree) == max_path_sum_brute(tree) == max_path_sum_iterative(tree), values
print("all max path sum tests passed")

Edge cases and pitfalls

• All values negative. The answer is the largest single value. Starting best at 0 would wrongly return 0, so start at minus infinity.
• Returning the bent path to the parent. The parent may only extend a one-branch chain; returning node.val + left + right produces paths that fork.
• Clamping the node itself. Clamp the child gains at 0, never the node’s own value: a path must contain at least one node.
• Recursion depth on long chains; use the iterative version or raise the limit consciously.

Where this shows up in data engineering

There is no direct pipeline equivalent. The technique, computing a local candidate at every node while returning a different, restricted value upward, is the general form of dynamic programming on trees. It appears in cost-based optimisation of plan trees, where each subtree reports its best cost under constraints to its parent.