124. Binary Tree Maximum Path Sum (Hard)

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge, and a node can appear at most once. The path does not need to pass through the root.

Given the root of a binary tree, return the maximum path sum of any non-empty path. Node values may be negative.

Example

• root = [1,2,3] → 6 (2 → 1 → 3)
• root = [-10,9,20,null,null,15,7] → 42 (15 → 20 → 7)

LeetCode 124 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Brute force, DFS from every node

For every node, treat it as the “top” of a path and compute the best path going down either side. Track the max across all nodes.

Python

def max_path_sum(root):
    def max_gain(node):              # L1: straight-down best path
        if not node:
            return 0
        left = max(0, max_gain(node.left))   # L2: O(n) subtree walk
        right = max(0, max_gain(node.right)) # L3: O(n) subtree walk
        return node.val + max(left, right)

    best = float('-inf')

    def visit(node):
        nonlocal best
        if not node:
            return
        left = max(0, max_gain(node.left))   # L4: O(n) per node
        right = max(0, max_gain(node.right)) # L5: O(n) per node
        best = max(best, node.val + left + right)  # L6: O(1) update
        visit(node.left)                     # L7: recurse
        visit(node.right)

    visit(root)
    return best

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function maxPathSum(root: TreeNode | null): number {
    function maxGain(node: TreeNode | null): number {  // L1: straight-down best path
        if (!node) return 0;
        const left = Math.max(0, maxGain(node.left));   // L2: O(n) subtree walk
        const right = Math.max(0, maxGain(node.right)); // L3: O(n) subtree walk
        return node.val + Math.max(left, right);
    }
    let best = -Infinity;
    function visit(node: TreeNode | null): void {
        if (!node) return;
        const left = Math.max(0, maxGain(node.left));   // L4: O(n) per node
        const right = Math.max(0, maxGain(node.right)); // L5: O(n) per node
        best = Math.max(best, node.val + left + right); // L6: O(1) update
        visit(node.left);                               // L7: recurse
        visit(node.right);
    }
    visit(root);
    return best;
}

Swift

final class Solution { func maxPathSum(_ root: TreeNode?) -> Int { guard let root else { return Int.min }; return max(pathThrough(root), max(maxPathSum(root.left), maxPathSum(root.right))) }; private func pathThrough(_ node: TreeNode) -> Int { node.val + max(0, downward(node.left)) + max(0, downward(node.right)) }; private func downward(_ node: TreeNode?) -> Int { guard let node else { return 0 }; return node.val + max(0, max(downward(node.left), downward(node.right))) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L4/L5 (max_gain calls)	$O(n)$	n nodes	$O(n²)$ ← dominates
L6 (update best)	$O(1)$	n	$O(n)$
L7 (visit recurse)	$O(1)$ dispatch	n	$O(n)$

max_gain is called freshly for every node visited by visit. In a balanced tree that’s $O(n log n)$ total; in a skewed tree it’s $O(n²)$.

Complexity

• Time: $O(n²)$. max_gain called at every node, each call $O(n)$, driven by L4/L5.
• Space: $O(h)$ recursion.

Approach 2: Single DFS with side-effect accumulator (optimal)

At each node, compute the max “straight-down gain” the node can contribute to its parent, at most one of its children, since a path is simple. While doing so, also consider the path that passes through the current node (using both children) and update a running best.

Python

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

    def max_gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, max_gain(node.left))          # L1: recurse left, O(1) dispatch
        right = max(0, max_gain(node.right))         # L2: recurse right, O(1) dispatch
        # best path passing through this node (uses both children)
        best = max(best, node.val + left + right)    # L3: O(1) side-effect update
        # return straight-down gain (one child at most) to the parent
        return node.val + max(left, right)           # L4: O(1) return

    max_gain(root)
    return best

TypeScript

function maxPathSum(root: TreeNode | null): number {
    let best = -Infinity;

    function maxGain(node: TreeNode | null): number {
        if (!node) return 0;
        const left = Math.max(0, maxGain(node.left));          // L1: recurse left, O(1) dispatch
        const right = Math.max(0, maxGain(node.right));         // L2: recurse right, O(1) dispatch
        // best path passing through this node (uses both children)
        best = Math.max(best, node.val + left + right);         // L3: O(1) side-effect update
        // return straight-down gain (one child at most) to the parent
        return node.val + Math.max(left, right);               // L4: O(1) return
    }

    maxGain(root);
    return best;
}

Swift

final class Solution { func maxPathSum(_ root: TreeNode?) -> Int { var best = Int.min; func gain(_ node: TreeNode?) -> Int { guard let node else { return 0 }; let left = max(0, gain(node.left)); let right = max(0, gain(node.right)); best = max(best, node.val + left + right); return node.val + max(left, right) }; _ = gain(root); return best } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L2 (recurse children)	$O(1)$ dispatch	n	$O(n)$
L3 (update best)	$O(1)$	n	$O(n)$
L4 (compute return val)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Each node is visited exactly once. The combination of “return local gain” and “update global best” eliminates all redundant traversal.

Complexity

• Time: $O(n)$. Each node visited once, driven by L1/L2.
• Space: $O(h)$ recursion.

The three moving parts

1. Return value: node.val + max(left, right), the best path including this node that can continue up to the parent. Can only use one child.
2. Side-effect update: node.val + left + right, the best path peaking at this node. Uses both children.
3. max(0, ...): negative subtree contributions are ignored; we pretend that branch isn’t there.

This is the same pattern as problem 543 (Diameter of Binary Tree), refined for weighted paths.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS from every node	$O(n²)$	$O(h)$
Single DFS with accumulator	$O(n)$	$O(h)$

This pattern, DFS returns a “local gain to parent,” side-effect tracks “global best through this node”, is one of the most important templates in tree DP. It also solves problem 543 and 687.

Test cases

Python

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def max_path_sum(root):
    best = float('-inf')
    def max_gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, max_gain(node.left))
        right = max(0, max_gain(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    max_gain(root)
    return best

def _run_tests():
    assert max_path_sum(build_tree([1, 2, 3])) == 6
    assert max_path_sum(build_tree([-10, 9, 20, None, None, 15, 7])) == 42
    # single node
    assert max_path_sum(build_tree([1])) == 1
    # all negative: must pick least negative
    assert max_path_sum(build_tree([-3, -1, -2])) == -1
    # negative root, positive children: best path is 2 + (-1) + 3 = 4
    assert max_path_sum(build_tree([-1, 2, 3])) == 4
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function maxPathSum(root: TreeNode | null): number {
    let best = -Infinity;
    function maxGain(node: TreeNode | null): number {
        if (!node) return 0;
        const left = Math.max(0, maxGain(node.left));
        const right = Math.max(0, maxGain(node.right));
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    }
    maxGain(root);
    return best;
}

console.assert(maxPathSum(buildTree([1, 2, 3])) === 6);
console.assert(maxPathSum(buildTree([-10, 9, 20, null, null, 15, 7])) === 42);
console.assert(maxPathSum(buildTree([1])) === 1);
console.assert(maxPathSum(buildTree([-3, -1, -2])) === -1);
console.assert(maxPathSum(buildTree([-1, 2, 3])) === 4);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, tree DP with side-effect accumulator

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.