Binary Tree Maximum Path Sum

hardTrees: BST & Advanced52 stepsJava · Python · C++

A path can bend at most once, at its highest node. For each node, compute the best downward path from it (node + max(0, left, right)) and, separately, the best path bending there (node + left + right, dropping negative sides). Track the best bend seen.

▶ Watch the animated trace

Traced input: root = [-10, 9, 20, null, null, 15, 7] → 42. Original problem: neetcode.io/problems/binary-tree-maximum-path-sum

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(h)

One post-order traversal.

Key idea

Return to the parent only a single downward branch, because a path can't fork twice.
Clamp negative branch sums to 0: skipping a branch is better than taking it.
Update the global answer with both branches at the current node.
Initialise the answer to the smallest int so all-negative trees work.

Common mistakes

Initialising the best to 0 fails for trees with only negative values.
Returning node + left + right to the parent creates an invalid forked path.

Solution

Java

int bestSum;

int maxPathSum(TreeNode root) {
    bestSum = Integer.MIN_VALUE;
    gain(root);
    return bestSum;
}

int gain(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, gain(node.left));
    int right = Math.max(0, gain(node.right));
    bestSum = Math.max(bestSum, node.val + left + right);
    return node.val + Math.max(left, right);
}

Python

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

    def gain(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node: return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

C++

int bestSum;

int gain(TreeNode* node) {
    if (!node) return 0;
    int left = max(0, gain(node->left));
    int right = max(0, gain(node->right));
    bestSum = max(bestSum, node->val + left + right);
    return node->val + max(left, right);
}

int maxPathSum(TreeNode* root) {
    bestSum = INT_MIN;
    gain(root);
    return bestSum;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All negative The best path is the single node -1.	`root = [-3, -2, -1]`	`-1`
Single node A path of one node.	`root = [5]`	`5`
Small positive tree 2 → 1 → 3 bends at the root.	`root = [1, 2, 3]`	`6`
Skip a negative child The -1 branch is clamped to 0.	`root = [2, -1]`	`2`