Binary Tree Maximum Path Sum

Approach Summary

Post-order DFS returns max gain from each node. At each node, consider the path through it (left + node + right) to update global max.

Full Solution & Approach

A path can start and end anywhere, so the maximum path is the best "gainer" through some node: node.val plus the best downward gain from each child. Use post-order recursion where each node returns the maximum gain that starts at this node and goes down one side: max(0, best_gain(left)) + node.val + max(0, best_gain(right)) — the max(0, …) lets a negative subtree be skipped entirely. While computing, update a global best with the full through-node value: node.val + max(0, left_gain) + max(0, right_gain). The node then returns only node.val + max(left_gain, right_gain) to its parent, since a parent path can use only one side. The recursion must consider every node as a potential turning point, which is exactly why the global best is updated at every node rather than only at the root.

Every node is visited once in post-order — O(n) time. Recursion depth equals the height — O(h) space, worst case O(n) for a skewed tree.

Solution Code

Solution

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

    def gain(node) -> int:
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

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

public int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    gain(root, best);
    return best[0];
}

private int gain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Math.max(0, gain(node.left, best));
    int right = Math.max(0, gain(node.right, best));
    best[0] = Math.max(best[0], node.val + left + right);
    return node.val + Math.max(left, right);
}

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    gain(root, best);
    return best;
}

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

Edge Cases to Watch

All negative values — the answer is the least-negative node (the max(0, …) logic keeps it reachable)
Single node — the node value itself
A path that turns at a node — captured by the through-node update
Zero-value nodes — skipped contributions are fine

How to Recognize This Pattern

Max path sum through any node
Post-order with global variable

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)