Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum is LeetCode 124 (Hard). A path is a sequence of nodes where each pair of neighbours is joined by an edge, and no node appears twice. Given the root of a binary tree, return the largest sum of values along any non-empty path.
- The path does not have to pass through the root, and it does not have to reach a leaf.
- Node values can be negative, so the answer can be negative too.
With up to 3 · 10⁴ nodes, trying every pair of endpoints is too slow; the target is one O(n) traversal.
- The number of nodes in the tree is in the range [1, 3 * 10⁴].
- -1000 <= Node.val <= 1000
Intuition
Every path has exactly one highest node, where it bends: up one side, through that node, down the other. So the binary tree maximum path sum is the best result of trying each node as the bend.
At every node, one post-order pass computes two numbers:
- Path bending here: the node's value plus the best downward run into each child, dropping any run that would subtract.
- Run handed to the parent: the value plus only one side, because a path that already uses both children cannot also continue up.
This is the shape of every "best path anywhere in a tree" problem: the recursion returns a one-sided value to the parent, while a separate variable records the two-sided answer at each node. Diameter of Binary Tree is the same pattern with edge counts instead of sums, and Longest Univalue Path adds an equality check. If the value a node returns is not the value you want as the answer, split them like this.
Approach
Before reading on: in [-10,9,20,null,null,15,7] the answer is 42 (15 → 20 → 7). Which node is the bend of that path? What should node 20 report to its parent, and why can it not be 42?
Start best at minus infinity
best holds the largest path sum seen so far. Start it below every possible sum: with all-negative values the answer is the largest single node, which is still negative, so a start of 0 would be wrong.
Get each child's gain, clamped at 0
Recurse into both children first. A child's gain is the best downward run starting at that child; if it is negative, use 0 instead, which means the path does not go that way at all. An empty child gives 0.
Try this node as the bend
node.val + left + right is the best path whose highest node is this one. Compare it with best and keep the larger. Once every node has been tried as the bend, best holds the answer.
Return one side to the parent
Return node.val + max(left, right). The parent can extend only one branch: a path that already went down both sides of this node cannot also go up without reusing it.
Answer with best
After gain(root) finishes, return best, not the root's return value. Each node does O(1) work once, so the max path sum takes O(n) time and O(h) stack for the recursion.
Binary Tree Maximum Path Sum solution in Python | C++ | Java
best starts at minus infinity because every node value may be negative.best becomes 2.best becomes 3.best becomes 6.best, not this return.best starts at minus infinity because every node value may be negative.best becomes 9.best becomes 15.best = 15, so it stays.best becomes 42.best = 42, so it stays.best, not this return.best starts at minus infinity because every node value may be negative.best becomes -1.best = -1, so it stays.best, not this return.Common pitfalls
Returning both sides to the parent
return node.val + left + right
return node.val + max(left, right)
A path that goes down both sides of a node cannot also go up to its parent; it would use the node twice. For [1,2,3,4,5], node 2 would report 4 + 2 + 5 = 11, and the root would build a 15 that is not a real path. The answer is 11.
Not clamping negative gains
left = gain(node.left) right = gain(node.right)
left = max(gain(node.left), 0) right = max(gain(node.right), 0)
A negative branch only lowers the sum, and a path is allowed to stop at any node. For [2,-1] the unclamped version returns 1 instead of 2.
Starting best at 0
best = 0
best = float("-inf")The path must contain at least one node. For [-3] the answer is -3, but a start of 0 is never beaten and the code returns 0, the sum of an empty path.
Complexity
Binary Tree Maximum Path Sum FAQ
Does the maximum path have to go through the root?
No. The path can bend at any node, which is why each node is tried as the bend and the answer is kept in best. In [-10,9,20,null,null,15,7] the best path, 15 → 20 → 7, never touches the root.
How is the binary tree maximum path sum LeetCode problem different from Path Sum?
Path Sum (LeetCode 112) only checks root-to-leaf paths against a target. Here a path can start and end anywhere and can bend at one node, and you want the largest sum rather than a yes or no.