Binary Tree Maximum Path Sum
Last Updated: March 29, 2026
Understanding the Problem
We need to find a path in a binary tree that gives the maximum sum. The path can start and end at any node, it does not have to go through the root, and it does not have to go from a leaf to another leaf. The only rule is that the path must follow parent-child edges and cannot visit a node more than once.
The tricky part is the shape of a valid path. In a tree, any path looks like an inverted "V" (or a straight line, which is a degenerate case). It goes up from some node to an ancestor, then possibly back down through the other child. So at any node, the path either passes through it as a "bend point" (using both left and right subtrees), or it continues upward through one side only.
The key observation: at each node, we need to make two different decisions. First, what is the best path that bends at this node (left + node + right)? That is a candidate for the global answer. Second, what is the best path we can report upward to the parent? That can only include one side, because a path cannot fork.
Key Constraints:
1 <= number of nodes <= 3 * 10^4- We need an O(n) or O(n log n) solution. Anything quadratic should work but O(n) is ideal and achievable.-1000 <= Node.val <= 1000- Node values can be negative. This is critical because it means including a subtree might actually hurt the sum. We need to handle the case where the best move is to skip a subtree entirely.
Approach 1: Brute Force (Enumerate All Paths)
Intuition
The most straightforward approach is to consider every pair of nodes as the endpoints of a path, find the path between them, compute its sum, and track the maximum. In a tree, there is exactly one path between any two nodes, so we just need to find it and sum up the values.
For each pair of nodes (u, v), the path goes from u up to their lowest common ancestor (LCA), then down to v. We can find the LCA and compute the path sum for each pair.
But wait, the path can also be a single node. So we also need to consider every individual node as a path of length zero.
Algorithm
- Collect all nodes in the tree.
- For every pair of nodes (u, v), find their lowest common ancestor.
- Compute the path sum from u to LCA to v.
- Track the maximum path sum across all pairs.
- Return the maximum.
Example Walkthrough
Input:
All possible paths and their sums: node 1 alone (sum=1), node 2 alone (sum=2), node 3 alone (sum=3), path 2->1 (sum=3), path 1->3 (sum=4), path 2->1->3 (sum=6).
Output:
Code
- Time Complexity: O(n^3). We have O(n^2) pairs of nodes, and for each pair, finding the LCA and computing the path sum each take O(n). So the total is O(n^2) * O(n) = O(n^3).
- Space Complexity: O(n). We store all n nodes in a list, and the recursion stack can go up to O(n) deep for a skewed tree.
This approach works but is far too slow for the given constraints. What if instead of thinking about pairs of endpoints, we thought about each node as a potential "bend point" of the path and computed everything in a single DFS?
Approach 2: DFS with Global Maximum (Optimal)
Intuition
Here is the key insight that unlocks this problem. Instead of thinking about path endpoints, think about the "top" of the path, the node where the path bends. Every path in a tree has exactly one highest node. At that node, the path either goes down into the left subtree, the right subtree, or both.
So at each node, we ask: "What is the best path that has THIS node as its highest point?" That path equals: best gain from the left child + node's value + best gain from the right child. We compare this against our global maximum.
But when reporting a value upward to the parent, we can only go in one direction. A path cannot fork, so we report: node's value + max(left gain, right gain). The parent will then extend this path further.
The beauty of this approach is that one post-order DFS handles everything. At each node, we compute the "gain" (the maximum sum we can achieve going downward from this node along a single branch), update the global answer by considering the "fork" path, and return the single-branch gain to the parent.
One more detail: if a subtree's gain is negative, we clamp it to zero. There is no point in extending a path into a subtree that reduces the total sum. We just skip it.
The trick is the dual role each node plays during the DFS. Locally, it considers the fork path (left + self + right) and updates the global answer. But it only reports a single-branch gain to its parent, because a path in a tree cannot split. This means we explore every possible path shape exactly once: at the node where that path reaches its highest point.
Clamping gains to zero handles negative subtrees elegantly. If a subtree's best contribution is negative, it is better to not extend into it at all. The max(gain, 0) ensures we just ignore it.
Algorithm
- Initialize a global variable
maxSumto negative infinity. - Define a recursive function
maxGain(node)that returns the maximum gain achievable by going downward fromnodealong a single branch. - For a null node, return 0 (no gain).
- Recursively compute
leftGain = max(maxGain(node.left), 0)andrightGain = max(maxGain(node.right), 0). Clamping to 0 means we skip negative subtrees. - Compute the "fork path" sum:
node.val + leftGain + rightGain. UpdatemaxSumif this is larger. - Return
node.val + max(leftGain, rightGain)to the parent, since we can only extend the path in one direction. - After the DFS completes, return
maxSum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the DFS. At each node, we do O(1) work (comparisons and additions). So the total is O(n).
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. For a balanced tree, h = O(log n). For a skewed tree, h = O(n) in the worst case.