Binary Tree Maximum Path Sum

The subtlety here is that a path is allowed to “bend” at exactly one node — going up one child and down the other — but once it bends it cannot bend again, because no node may repeat. That means two different quantities matter at every node: the best path through it (which can use both children, and is a valid final answer), and the best path extending upward from it to an ancestor (which can only use one child, since the ancestor still needs to attach on the other side).

Brute Force (best downward path from every node)

Time O(n^2)Space O(h)

For every node, compute the best sum starting at that node and going straight down (through at most one child at a time), then combine the current node with its two “best downward” child values to get a bend-through-this-node candidate. Take the max over all nodes.

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def best_downward(node: TreeNode | None) -> int:
            if node is None:
                return 0
            return node.val + max(0, best_downward(node.left), best_downward(node.right))

        def best_through(node: TreeNode | None) -> int:
            if node is None:
                return float("-inf")
            through = node.val + max(0, best_downward(node.left)) + max(0, best_downward(node.right))
            return max(through, best_through(node.left), best_through(node.right))

        return best_through(root)

Complexity: best_downward walks a whole subtree and is called (twice) from every node via best_through → O(n^2) time worst case. Recursion depth → O(h) space.

Single Pass (gain function + global max)

OptimalTime O(n)Space O(h)

Fold both quantities into one post-order DFS. The function’s return value is the “best downward path starting at this node” (what a parent is allowed to use — clamped at 0, since a negative contribution should just be dropped). As a side effect, before returning, it also checks the “bend through this node” value (using both children, unclamped-combination-then-added-to-node) against a running global best.

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        best = float("-inf")

        def gain(node: TreeNode | None) -> int:
            nonlocal best
            if node is None:
                return 0
            left_gain = max(gain(node.left), 0)
            right_gain = max(gain(node.right), 0)
            best = max(best, node.val + left_gain + right_gain)
            return node.val + max(left_gain, right_gain)

        gain(root)
        return best

Tracing root = [-10,9,20,null,null,15,7]:

-10

1 / 4

comparingseenresultdiscarded

Node 9 is a leaf: left_gain=right_gain=0. best updates to max(-inf, 9)=9. Returns gain 9.

Complexity: gain is called exactly once per node, doing O(1) work beyond its children’s results → O(n) time. Recursion depth → O(h) space.