Binary Tree Maximum Path Sum

hard tree dfs dp

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. The path sum of a path is the sum of the node's values in the path.

For each node, the best path that passes through it equals node.val + max(0, gain(left)) + max(0, gain(right)). The best path that continues upward from this node uses only one side: gain(node) = node.val + max(0, max(gain(left), gain(right))). Track a global best while computing gains in a single post-order DFS.

Inputlevel-order: [-10, 9, 20, _, _, 15, 7]

Output42

Path 15 → 20 → 7 sums to 42.

level-order ('_' for null)

def max_path_sum(root):
    best = [float("-inf")]
    def gain(node):
        if node is None: return 0
        l = max(0, gain(node.left))
        r = max(0, gain(node.right))
        best[0] = max(best[0], node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best[0]

function maxPathSum(root) {
  let best = -Infinity;
  function gain(node) {
    if (!node) return 0;
    const l = Math.max(0, gain(node.left));
    const r = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + l + r);
    return node.val + Math.max(l, r);
  }
  gain(root);
  return best;
}

class Solution {
    int best = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) { gain(root); return best; }
    int gain(TreeNode node) {
        if (node == null) return 0;
        int l = Math.max(0, gain(node.left));
        int r = Math.max(0, gain(node.right));
        best = Math.max(best, node.val + l + r);
        return node.val + Math.max(l, r);
    }
}

int best = INT_MIN;
int gain(TreeNode* node) {
    if (!node) return 0;
    int l = max(0, gain(node->left));
    int r = max(0, gain(node->right));
    best = max(best, node->val + l + r);
    return node->val + max(l, r);
}

Explanation

A path can wander up and down through the tree, so the key insight is to separate two ideas: the best path that bends at a node (uses both children) versus the best path that continues upward from a node (uses just one child).

The helper gain(node) returns the largest sum of a downward path that starts at node and goes down one side. For each child we compute its gain but clamp it with max(0, ...) so a negative subtree is simply ignored rather than dragging the sum down.

While computing, we also consider the path that bends at this node: node.val + l + r where l and r are the (clamped) child gains. We compare that to a global best. But the value we return upward is node.val + max(l, r), because a path passing through the parent can only use one of our sides.

Example: tree [-10, 9, 20, _, _, 15, 7]. At node 20, children 15 and 7 give gains 15 and 7, so the bending path is 20 + 15 + 7 = 42, which becomes best. Node 20 returns 20 + 15 = 35 upward, and the root's negative value can't beat 42.

One post-order pass visits each node once, so the algorithm is O(n) time.

Time: O(n) Space: O(h) recursion depth