What is the optimal time complexity of Binary Tree Maximum Path Sum?

The most efficient approach in this guide ("DFS with Global Maximum") runs in O(n) time and uses O(h) where h is the height of the tree extra space.

What pattern does Binary Tree Maximum Path Sum use?

Binary Tree Maximum Path Sum is a hard-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Binary Tree Maximum Path Sum — Solution in C++, Java, Python, Go

Worked solution with intuition, algorithm, and verified code in C++, Java, Python, and Go.

Approach 1

DFS with Global Maximum

Intuition

The key insight is that at each node, we have two decisions to make: what is the best path sum that passes through this node (potentially using both subtrees), and what is the best path sum we can return to the parent (using at most one subtree). We use a global variable to track the overall maximum path sum. For each node, we compute the maximum gain from its left and right subtrees (clamping negative gains to zero since we can choose not to extend the path). The path through the current node is node.val + leftGain + rightGain, which we compare against our global maximum. We return node.val + max(leftGain, rightGain) to the parent, since a path through the parent can only use one branch.

Algorithm

Initialize a global maximum variable to negative infinity.
Define a recursive helper function that returns the maximum gain from a subtree.
For a null node, return 0.
Recursively compute the maximum gain from the left subtree (clamp to 0 if negative).
Recursively compute the maximum gain from the right subtree (clamp to 0 if negative).
Update the global maximum with node.val + leftGain + rightGain.
Return node.val + max(leftGain, rightGain) to the caller.
Call the helper on root and return the global maximum.

TimeO(n)SpaceO(h) where h is the height of the tree

Code (C++ · Java · Python · Go)

C++17

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

private:
    int maxGain(TreeNode* node, int& maxSum) {
        if (node == nullptr) return 0;
        int leftGain = max(0, maxGain(node->left, maxSum));
        int rightGain = max(0, maxGain(node->right, maxSum));
        maxSum = max(maxSum, node->val + leftGain + rightGain);
        return node->val + max(leftGain, rightGain);
    }
};

Java 21

class Solution {
    private int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0, maxGain(node.right));
        maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
        return node.val + Math.max(leftGain, rightGain);
    }
}

Python 3.12

def maxPathSum(root: Optional[TreeNode]) -> int:
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(0, max_gain(node.left))
        right_gain = max(0, max_gain(node.right))
        max_sum = max(max_sum, node.val + left_gain + right_gain)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

Go 1.26

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt64
    var maxGain func(*TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftGain := max(0, maxGain(node.Left))
        rightGain := max(0, maxGain(node.Right))
        pathSum := node.Val + leftGain + rightGain
        if pathSum > maxSum {
            maxSum = pathSum
        }
        return node.Val + max(leftGain, rightGain)
    }
    maxGain(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Binary Tree Maximum Path Sum

Examples

Example 1

Example 2

Constraints

Approaches