Binary Tree Maximum Path Sum

Problem

A path goes through any sequence of nodes along parent-child connections. Return the max sum of any path.

Key insight: Post-order DFS. Each node contributes node.val + max(left_gain, 0) + max(right_gain, 0) to the global max. But returns only one side to parent.

Solutions

// C
int maxSum;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = dfs(node->left), r = dfs(node->right);
    if (l < 0) l = 0;
    if (r < 0) r = 0;
    int cur = node->val + l + r;
    if (cur > maxSum) maxSum = cur;
    return node->val + (l > r ? l : r);
}
int maxPathSum(TreeNode* root) {
    maxSum = INT_MIN;
    dfs(root);
    return maxSum;
}

// C++
int maxSum = INT_MIN;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = max(0, dfs(node->left));
    int r = max(0, dfs(node->right));
    maxSum = max(maxSum, node->val + l + r);
    return node->val + max(l, r);
}
int maxPathSum(TreeNode* root) {
    maxSum = INT_MIN;
    dfs(root);
    return maxSum;
}

// Java
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    dfs(root); return maxSum;
}
int dfs(TreeNode node) {
    if (node == null) return 0;
    int l = Math.max(0, dfs(node.left));
    int r = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, node.val + l + r);
    return node.val + Math.max(l, r);
}

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

# Python
def maxPathSum(root):
    max_sum = [float('-inf')]
    def dfs(node):
        if not node:
            return 0
        l = max(0, dfs(node.left))
        r = max(0, dfs(node.right))
        max_sum[0] = max(max_sum[0], node.val + l + r)
        return node.val + max(l, r)
    dfs(root)
    return max_sum[0]

Complexity

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

Key Insight

Key distinction: the path through a node can use both children (for global max update), but can only extend one direction upward (return to parent).