Difficulty: Hard · LeetCode 124

Problem

Return maximum path sum of any non-empty path in a binary tree.

Understanding the problem

A path can split through current node (left + val + right), but extending to parent can only take ONE branch (val + max(left, right)). Clamp negative branch gains to 0.

Intuition

Single DFS computing gain to return upward and updating global max path sum.

Approach

Initialize answer = -inf.
Define dfs(node): get left = max(0, dfs(node.left)), right = max(0, dfs(node.right)).
Update answer = max(answer, node.val + left + right).
Return single branch gain: node.val + max(left, right).

Naive Solution

For every node, calculate maximum gain separately.

Python

class Solution:
    def maxPathSum(self, root):

        def gain(node):
            if not node:
                return 0

            return node.val + max(
                0,
                gain(node.left),
                gain(node.right)
            )

        def path(node):
            if not node:
                return -float("inf")

            left = gain(node.left)
            right = gain(node.right)

            current = node.val + max(0, left) + max(0, right)

            return max(
                current,
                path(node.left),
                path(node.right)
            )

        return path(root)

C++

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        return path(root);
    }

private:
    int gain(TreeNode* node) {
        if (!node) return 0;

        return node->val + max({0, gain(node->left), gain(node->right)});
    }

    int path(TreeNode* node) {
        if (!node) return INT_MIN;

        int left = gain(node->left);
        int right = gain(node->right);

        int current = node->val + max(0, left) + max(0, right);

        return max({current, path(node->left), path(node->right)});
    }
};

Java

class Solution {
    public int maxPathSum(TreeNode root) {
        return path(root);
    }

    private int gain(TreeNode node) {
        if (node == null) return 0;

        return node.val + Math.max(0, Math.max(gain(node.left), gain(node.right)));
    }

    private int path(TreeNode node) {
        if (node == null) return Integer.MIN_VALUE;

        int left = gain(node.left);
        int right = gain(node.right);

        int current = node.val + Math.max(0, left) + Math.max(0, right);

        return Math.max(current, Math.max(path(node.left), path(node.right)));
    }
}

JavaScript

var maxPathSum = function(root) {
    const gain = (node) => {
        if (!node) return 0;

        return node.val + Math.max(0, gain(node.left), gain(node.right));
    };

    const path = (node) => {
        if (!node) return -Infinity;

        const left = gain(node.left);
        const right = gain(node.right);

        const current = node.val + Math.max(0, left) + Math.max(0, right);

        return Math.max(current, path(node.left), path(node.right));
    };

    return path(root);
};

Time: O(n^2) worst case · Aux Space: O(h)

Optimized Code (Python 3)

Python

class Solution:
    def maxPathSum(self, root):
        answer = -float("inf")

        def dfs(node):
            nonlocal answer

            if not node:
                return 0

            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))

            current = node.val + left + right

            answer = max(answer, current)

            return node.val + max(left, right)

        dfs(root)
        return answer

C++

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int answer = INT_MIN;
        dfs(root, answer);
        return answer;
    }

private:
    int dfs(TreeNode* node, int& answer) {
        if (!node) return 0;

        int left = max(0, dfs(node->left, answer));
        int right = max(0, dfs(node->right, answer));

        int current = node->val + left + right;

        answer = max(answer, current);

        return node->val + max(left, right);
    }
};

Java

class Solution {
    private int answer;

    public int maxPathSum(TreeNode root) {
        answer = Integer.MIN_VALUE;
        dfs(root);
        return answer;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        int current = node.val + left + right;

        answer = Math.max(answer, current);

        return node.val + Math.max(left, right);
    }
}

JavaScript

var maxPathSum = function(root) {
    let answer = -Infinity;

    const dfs = (node) => {
        if (!node) return 0;

        const left = Math.max(0, dfs(node.left));
        const right = Math.max(0, dfs(node.right));

        const current = node.val + left + right;

        answer = Math.max(answer, current);

        return node.val + Math.max(left, right);
    };

    dfs(root);
    return answer;
};

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

Takeaway

Critical Pattern: Two values: Best path through current node → update answer; Best path going upward → return one branch only.