LeetCode 124 · Trees

Binary Tree Maximum Path Sum, explained with a picture

The richest trail through a tree of coins.

HardTrees
▶ Watch it step by step

The problem

A path is any chain of connected nodes (each used at most once); it doesn’t need to pass through the root. Find the largest possible sum of values along a path.

Input:  [−10, 9, 20, null, null, 15, 7]
Output: 42   (15 → 20 → 7)

Picture it

Picture a tree of coins, where negative values are debts. Each node reports to its parent the best one-way trail going down from it (and ignores a side that would lose money, i.e. treats it as 0). At each node we also try the bent trail left + me + right as a candidate answer.

How to recognise it

  • A path may start and end anywhere and bend once at its highest node, so it need not touch the root or a leaf.
  • Values can be negative, so a longer path is not always better: sometimes a branch should be left out.
  • Like the diameter problem, each node needs one number from each child (the best straight path going down), and a bent path is completed at its top node.
  • Up to 3 × 10^4 nodes, so do O(1) work per node.

Start with brute force

Every path has a highest node where it bends. For each node, compute the best downward path from each child with a separate helper, keep only positive ones, and add the node's value.

def down(node):                       # best path starting here, going down
    if not node:
        return 0
    return node.val + max(0, down(node.left), down(node.right))

def max_path_brute(root):
    best = -inf
    def visit(node):
        nonlocal best
        if not node:
            return
        bend = node.val + max(0, down(node.left)) + max(0, down(node.right))
        best = max(best, bend)
        visit(node.left)
        visit(node.right)
    visit(root)
    return best

Each down call walks a whole subtree, once for every ancestor: O(n log n) on a balanced tree, O(n²) on a chain, about 4.5 × 10^8 steps for 3 × 10^4 nodes. Too slow.

From brute force to the idea

  1. Find the waste. down(child) is recomputed at every ancestor, although it never changes.
  2. Compute it once, bottom-up. gain(node) returns the best downward path starting at node. The parent receives it as a return value.
  3. Drop losing branches. max(gain(child), 0) means "use this branch only if it adds something". A child path with a negative sum is replaced by 0, that is, not taken.
  4. Record the bend. With l and r in hand, node.val + l + r is the best path whose highest node is this one. Keep the best in best.
  5. Return a straight path. The parent can extend only one branch, so return node.val + max(l, r).

This is the key idea: one DFS returns the best straight path down, while each node also records the best path that bends at it.

best must start at -inf (from math import inf, which the page leaves out), because the answer can be negative.

The key idea

DFS returns the best downward gain; update best with left + node + right, clamping negative gains to 0. O(n).

Python solution

def max_path_sum(root):
    best = -inf
    def gain(node):
        nonlocal best
        if not node:
            return 0
        l = max(gain(node.left), 0)     # ignore losing branches
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n log n) balanced, O(n²) chain: each downward gain recomputed per ancestorO(h): recursion only, h is the height
One DFS (shown code)O(n): each node visited once, O(1) workO(h): one stack frame per level, h = n for a chain

Edge cases

  • Single negative node ([-3]): returns −3; a path needs at least one node.
  • All negative ([-2, -1]): returns −1, the largest single value.
  • Negative child ([2, -1]): returns 2; the −1 branch is dropped.
  • Best path avoids the root ([-10, 9, 20, null, null, 15, 7]): returns 42 (15 → 20 → 7).
  • Very deep tree: a chain of about 1,000 nodes exceeds Python's default recursion limit (RecursionError), and LeetCode allows 3 × 10^4 nodes. Use an explicit stack (post-order) if needed.

Common mistakes

  • Starting best at 0, which returns 0 for an all-negative tree, although no empty path is allowed.
  • Returning node.val + l + r to the parent: a path that already bends cannot be extended.
  • Clamping the node's own value at 0. Only the child gains are optional; the node itself is always on the path.
  • Forgetting nonlocal best.
Your turn: best downward path

Return the largest sum of a path that only goes downwards: from some node to one of its descendants (or a single node), with no bend. For [-10, 9, 20, null, null, 15, 7] the answer is 35 (20 → 15). Describe your approach, then write it if you like.

Compare with our answer

Same bottom-up gain, but there is no bend to record: the best path starting at each node is itself a candidate.

from math import inf

def max_down_path(root):
    best = -inf
    def gain(node):
        nonlocal best
        if not node:
            return 0
        g = node.val + max(gain(node.left), gain(node.right), 0)
        best = max(best, g)
        return g
    gain(root)
    return best

Time O(n), space O(h).

A strong answer mentions: that the candidate at each node is the returned straight path, clamping child gains at 0, and starting best at minus infinity.

Check what stuck

1. A tree of rooms has a score per room (some negative). You must choose a connected route through rooms, each used once, with the best total. Which approach fits best?

2. Why does gain return node.val + max(l, r) but record node.val + l + r?

3. A learner starts with best = 0 instead of -inf. Which tree now gets a wrong answer?

Score 60% or more and the lesson is marked complete.