Binary Tree Maximum Path Sum

HardBinary Trees

Find the maximum sum of any path in a binary tree. A path is a sequence of connected nodes and need not pass through the root.

Open problem

Constraints

1 <= nodes <= 3 * 10^4
-1000 <= Node.val <= 1000

Post-order with downward gains

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

For each node compute the best path going down one side (ignoring negatives). The best path through a node is its value plus both downward gains; track the global maximum while returning only the single-sided gain upward.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<int(TreeNode*)> gain = [&](TreeNode* node) -> int {
        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);
    };
    gain(root);
    return best;
}