Binary Tree Maximum Path Sum (LeetCode 124)

The problem

You get the root of a binary tree whose values can be negative. A path is any sequence of connected nodes where each node appears at most once. It can start and end anywhere and doesn’t have to pass through the root. Return the largest sum of any non-empty path.

Input:  [-10, 9, 20, null, null, 15, 7]

        -10
        /  \
       9    20
           /  \
          15   7

Output: 42

The path 15 → 20 → 7 sums to 42. Including the root would only make it worse, because -10 costs more than 9 adds.

How to think about it

Start with brute force. Every path has a highest node where it bends. For each node, try every downward path on the left and every one on the right, and combine. Enumerating paths per node is O(n) each, so O(n²) overall, and it’s fiddly to write.

The key insight: it’s Diameter with values. At each node, two different quantities matter:

• What the node returns to its parent: the best path that starts here and goes down one side only, node.val + max(l, r). A parent can’t use a path that forks.
• What the node records as a candidate answer: the best path that bends here, node.val + l + r, kept in a global best.

Drop negative branches. If a child’s best downward gain is negative, including it only lowers the sum, so clamp it at 0: l = max(gain(left), 0). That’s the whole difference from Diameter, and it’s what handles negative values.

Which pattern is this? Tree DFS with “return one value, track another”. The tell is “path anywhere in the tree”, where the best path can bend at any node.

Approach

1. Keep best = -inf outside the recursion. Not 0: an all-negative tree’s answer is negative.
2. gain(node) returns 0 for an empty node.
3. Compute l = max(gain(left), 0) and r = max(gain(right), 0).
4. Update best with node.val + l + r, the path bending at this node.
5. Return node.val + max(l, r), the best one-sided path for the parent.
6. Call gain(root) and return best.

Solution

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        l = max(gain(node.left), 0); r = max(gain(node.right), 0)   # ignore branches that hurt
        best = max(best, node.val + l + r)                          # path that bends at this node
        return node.val + max(l, r)                                 # parent can extend only one side
    gain(root); return best
# max_path_sum(tree[-10,9,20,null,null,15,7]) -> 42

Dry run

On the example, in the order nodes finish:

The bend at 20 gives 42. The root’s bend (34) is smaller, so it doesn’t win.

Complexity

• Time: O(n). One post-order pass with O(1) work per node.
• Space: O(h). The recursion stack goes as deep as the tree height: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• All negative values. For [-3, -1, -2] the answer is -1, a single node. Starting best at 0 would wrongly return 0.
• Clamp the children, not the node. The node’s own value is always included (the path is non-empty); only optional branches are clamped at 0.
• Returning the bend upward is the classic bug. A parent must get val + max(l, r), never val + l + r.
• Single node returns its own value.

Related problems

• Diameter of Binary Tree (LeetCode 543): the same shape, counting edges instead of summing values.
• Path Sum (LeetCode 112): the restricted root-to-leaf version.
• Lowest Common Ancestor of a Binary Tree (LeetCode 236): another post-order DFS combining left and right results.