Binary Tree Maximum Path Sum

Problem Description

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 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.

Examples

Constraints

• The number of nodes in the tree is in the range [1, 3 * 10⁴].
• -1000 ≤ Node.val ≤ 1000

Choosing to Split or Extend at Every Node

For any node, there are two ways it can participate in the maximum path:

1. Extend: It can join a path coming from one of its children (left or right) and extend that path upward to its parent. In this case, the contribution of this node’s subtree is val + max(left_gain, right_gain).
2. Split: It can act as the highest point (turning point) of the path, connecting the left child’s path to the right child’s path. In this case, the path sum is val + left_gain + right_gain. This path cannot be extended further upward because doing so would require visiting the node twice.

To find the global maximum, we perform a post-order traversal. At each node, we compute the maximum gain it can extend upward. Simultaneously, we calculate the path sum if we split at this node, and update a global maximum variable with this value. We also ignore negative gains: if a child subtree yields a negative sum, we choose not to include it (gain is 0).

Solution 1: Post-Order DFS with Global Max Update

Recursively calculate child gains, updating the global maximum path sum at each step.

class Solution {
    private int maxPath = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        gain(root);
        return maxPath;
    }

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

        // ignore subtrees with negative path sum contributions
        int leftGain = Math.max(0, gain(node.left));
        int rightGain = Math.max(0, gain(node.right));

        // path sum if we split (turn) at the current node
        int splitSum = node.val + leftGain + rightGain;
        maxPath = Math.max(maxPath, splitSum);

        // return max gain if we extend the path upward
        return node.val + Math.max(leftGain, rightGain);
    }
}

class Solution:
    def __init__(self):
        self.max_path = float("-inf")

    def maxPathSum(self, root: TreeNode) -> int:
        def gain(node):
            if not node:
                return 0

            # ignore subtrees with negative path sum contributions
            left_gain = max(0, gain(node.left))
            right_gain = max(0, gain(node.right))

            # path sum if we split at the current node
            split_sum = node.val + left_gain + right_gain
            self.max_path = max(self.max_path, split_sum)

            # return max gain if we extend the path upward
            return node.val + max(left_gain, right_gain)

        gain(root)
        return self.max_path

#include <algorithm>
#include <climits>

class Solution {
private:
    int maxPath = INT_MIN;

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

        // ignore subtrees with negative path sum contributions
        int leftGain = std::max(0, gain(node->left));
        int rightGain = std::max(0, gain(node->right));

        // path sum if we split at the current node
        int splitSum = node->val + leftGain + rightGain;
        maxPath = std::max(maxPath, splitSum);

        // return max gain if we extend the path upward
        return node->val + std::max(leftGain, rightGain);
    }

public:
    int maxPathSum(TreeNode* root) {
        gain(root);
        return maxPath;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We visit each node exactly once.
• Space Complexity: O(h) where h is the tree height, representing the recursive call stack depth.

Where it breaks: If the tree contains only negative values, the global maximum initialization must be set to INT_MIN or float("-inf") to correctly find the least negative single-node path. If you initialize it to 0, the algorithm will return 0 on trees like [-3], which is incorrect.

Common Mistakes

• Initializing the global maximum to 0. If the tree only contains negative values (e.g. [-3]), the correct answer is -3. Initializing to 0 returns an incorrect answer.
• Including negative child gains. If gain(node.left) is -5, you must bound it to 0 using Math.max(0, leftGain). Failing to do so decreases the path sum.
• Attempting to extend a split path upward. The value returned to the parent must be node.val + max(leftGain, rightGain). Returning node.val + leftGain + rightGain is invalid because a path cannot branch into both children and also go up to the parent.

Frequently Asked Questions

Can the path consist of a single node? Yes. If a node has only negative neighbors, the maximum path sum is the value of the node itself, which is handled correctly by ignoring negative child gains.

Why is post-order traversal used here? We need the results from the left and right children before we can compute the gains and path sum for the current node. Post-order DFS (left, right, root) fits this dependency.

What does this problem test in interviews? It tests your capability to solve complex tree problems using bottom-up recursion, specifically managing state updates that do not match the return value of the recursive steps.

← All Problems