Binary Tree Maximum Path Sum

Practice here

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. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Approach#

• Intuition: Any maximum path must "turn" at exactly one node — the highest node on the path. At that turning node, the path can extend down into the left subtree, down into the right subtree, or both. This means you can decompose the problem: for each node, compute the best gain its left and right subtrees offer and combine them to check a global maximum.
• Mechanics: A post-order DFS computes the best single-arm extension each subtree can offer its parent — max(0, bestArm(left)) + root->val or the right equivalent. Negative subtree contributions are clamped to 0 (it is always better to not include them). At each node, leftArm + root->val + rightArm is compared against a running global maximum before returning only root->val + max(leftArm, rightArm) upward (a parent can only continue along one arm).
• Trade-off: A single O(n) pass with O(1) extra state (the global maxi) handles all possible path shapes uniformly. Naively enumerating all paths would cost O(n²) or worse.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSumUtil(TreeNode* root, int &maxi) {
        if(!root)
            return 0;
        
        // clamp to 0: if a subtree contributes negatively, don't include it
        int leftSum = max(0, maxPathSumUtil(root->left, maxi));
        int rightSum = max(0, maxPathSumUtil(root->right, maxi));

        // candidate: path that enters from left, passes through root, exits right
        // this path cannot be extended upward (uses both sides), so update global max here
        maxi = max(maxi, root->val + leftSum + rightSum);

        // return the best single-arm extension the parent can use
        // parent can only continue through one side (left OR right, not both)
        return root->val + max(leftSum, rightSum);
    }
    int maxPathSum(TreeNode* root) {
        int maxi = INT_MIN;
        maxPathSumUtil(root, maxi);
        return maxi;
    }
};

Time Complexity: O(n), visits every node once to compute the maximum path sum.

Space Complexity: O(h)

• This is due to the recursion stack, where h = height of the tree.
• In the worst case (skewed tree): h = n → O(n)
• In a balanced tree: h = log n