On this page

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge, and each node appears at most once. The path does not need to pass through the root. The path sum is the sum of the node values on it.

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

Constraints:

  • The number of nodes is in the range [1, 3 * 10^4].
  • -1000 <= Node.val <= 1000

Intuition

This is the diameter problem with sums instead of lengths, plus one twist: values can be negative.

Every path has a highest node where it turns. For that node, the best path through it is:

node value + best downward gain from the left + best downward gain from the right

A downward gain from a child is the best sum of a chain that starts at that child and goes down. If that gain is negative, we are better off not taking it, so we use max(0, gain).

Approach: DFS Returning the Best Downward Chain

Keep a global best, initialized to a very small number (not 0, because the answer can be negative).

  1. If the node is null, return 0.
  2. left = max(0, gain(node.left)) and right = max(0, gain(node.right)).
  3. Update best = max(best, node.val + left + right). This is the best path that turns at this node.
  4. Return node.val + max(left, right) to the parent. The parent can only extend one side, because a path cannot branch.

The key rule is the same as in diameter: the return value is a single chain, the updated answer uses both sides.

Code

class Solution {
int best;
int gain(TreeNode* node) {
if (node == nullptr) return 0;
int left = max(0, gain(node->left));
int right = max(0, gain(node->right));
best = max(best, node->val + left + right);
return node->val + max(left, right);
}
public:
int maxPathSum(TreeNode* root) {
best = INT_MIN;
gain(root);
return best;
}
};

Complexity

Time: O(n)

Each node is visited exactly once.

Space: O(h)

Recursion stack depth equals the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"This is the diameter pattern with sums, plus negative values to handle. Every path has a highest node. For each node I compute the best downward gain from the left and from the right, and I clamp each at zero, because a negative chain is better skipped. The best path turning at this node is the node value plus both gains, so I update a global maximum with that. But I return only the node value plus the larger single gain to the parent, because a path cannot branch. I initialize the global to negative infinity, not zero, since all values can be negative. Time is O of n and space is O of h."
Next TopicSame Tree