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 (both children’s already-clamped gains, plus the node value, without clamping the total) 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] (trace data lives in this problem folder’s data.ts). Watch the split at node 20: its bend-through path uses BOTH children and sets the answer, while the one value it returns upward uses only the better child, so a parent can still attach.

-10

Computing node–

gain from left–

gain from right–

bend through (vs best)–

best so far–

returned upward–

final answer–

1 / 7

seenresultcurrent

Post-order: each child reports one upward gain before its parent runs. Every node also checks its bend-through path as a candidate for best.

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.

Binary Tree Maximum Path Sum

Brute Force (best downward path from every node)

Single Pass (gain function + global max)

More Trees practice