Binary Tree Maximum Path Sum

Difficulty: Hard

Problem

A path in a binary tree is a chain of adjacent nodes in which no node is used more than once. It can start and end anywhere: it need not touch the root or finish at leaves. Since node values may be NEGATIVE, choose the chain whose values add up to the largest total, using at least one node, and return that total.

Example

Input: root = [-8,4,12,null,null,9,-3]
Output: 21
Explanation: The best chain is 9 → 12 = 21; the -3 child is left out because it only subtracts. Joining through the root would add -8 and the left value 4 for a lower total.

Brute-force approach

Enumerating all paths is exponential. There is no sane brute force. The one-pass gain recursion below is both the intuitive and the optimal solution.

Optimal approach

Key insight: Diameter counted edges; here we sum values. Each call returns the best straight chain DOWN, records the best bend THROUGH itself, and drops any branch that would lose money.

One postorder pass: each node computes its best downward chain (gain), records the best bend (node + both clamped gains) into a global best, and returns the chain to its parent.

Steps

  1. Track a global best, starting at −∞
  2. gain(null) = 0
  3. At each node: L = max(gain(left), 0), R = max(gain(right), 0)
  4. Record the bend: best = max(best, node.val + L + R)
  5. Return the chain: node.val + max(L, R)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function maxPathSum(root):
    best = ____
    
    function gain(node):
        if node is null:
            return 0
        L = max(gain(node.left), ____)
        R = max(gain(node.right), ____)
        
        best = max(best, node.val + ____ + ____)
        return node.val + ____
    
    gain(root)
    return best

Hints

  • A lone negative node must be able to win, what must best start at?
  • Losing branches are optional: clamp each child's gain against what?
  • The bend through this node uses BOTH clamped sides plus the node itself
  • The parent can extend only a STRAIGHT chain: the node plus its richer side

Complexity questions

What is the time complexity?

O(n): one gain computation per node. One postorder pass: each node does two clamps, one record, one return. The exponential space of 'all paths' is never enumerated: the bend decomposition covers every path implicitly.

What is the space complexity?

O(h): the recursion stack. Just the recursion stack (O(log n) balanced, O(n) skewed). No paths are ever materialized, only two numbers per frame.

Why must best start at −∞ instead of 0?

All-negative trees: the path must contain at least one node, so the answer can be negative. Best = 0 would report a nonexistent empty path. On [-3], every bend candidate is -3, and best must end up -3. Starting at 0 would return 0: the sum of a path with zero nodes, which the problem forbids.

Diameter and Max Path Sum share a skeleton. What are its two roles?

RETURN a straight-chain quantity the parent can extend; RECORD a bend quantity globally at every node. That's the whole pattern: chains go up (extendable), bends stay local (finished candidates). Recognize it and problems like 'longest univalue path' or 'count good paths' become variations, not mysteries.

Check your understanding of Binary Tree Maximum Path Sum

What counts as a path in this problem?

Any connected sequence of nodes, anywhere in the tree, each used at most once. This is the loosest path definition yet: start anywhere, end anywhere, stay connected, never revisit. Even a single node counts as a path.

In [-10,9,20,null,null,15,7], why does the best path avoid the root?

Going through -10 costs 10: the through-root path 9 + (-10) + 35 = 34 loses to the subtree path 15 + 20 + 7 = 42. The best through-root path takes the left chain (9), the root (-10), and the best right chain (20+15=35): total 34. Staying inside the right subtree scores 42. Negative nodes CAN appear on a path. They just have to earn their place, and -10 doesn't.

Like the diameter's bend, the best path has a highest node. At that node, the candidate sum equals what?

node.val + gainLeft + gainRight, where gain is the best DOWNWARD chain sum from each side. Exactly the diameter formula with values instead of edge counts: the path climbs one chain, passes through the node, and descends the other chain. gain plays the role height played.

A subtree's best chain is NEGATIVE. What do we use instead, and why?

0: a path is never forced to extend into a losing branch: max(gain, 0) is the 'walk away' option. Extending into a branch is optional. If the best a branch can offer is a loss, the path simply doesn't go there, mathematically, clamp: max(gain, 0).

For the single-node tree [-3], what is the answer?

-3: a path must contain at least one node, so the best is the least-bad single node. The problem requires at least one node, an empty path isn't allowed. That's why the global best starts at negative infinity, not 0: a lone negative node must be able to win.

Related problems

Keep practising