Given the root of a binary tree, return the maximum sum of any path between any two nodes. A path doesn't need to pass through the root, and each node can appear in it at most once.
Example
Input root = [-10,9,20,null,null,15,7]
Output 42
Key Pointers
A path "through" a node can use both its left and right branches — but the node can only contribute one branch (not both) to whatever path continues upward to its parent.
Negative subtree contributions should be discarded (treated as 0) rather than included, since a path is never improved by adding a negative sum.
Track the best path seen anywhere with an outer variable, while the recursion itself returns only the best single-branch extension for its parent to use.
Step-by-Step Analysis
Keep a variable best = -infinity outside the recursion.
Define gain(node); base case None returns 0.
Recursively compute left_gain = max(gain(node.left), 0) and right_gain = max(gain(node.right), 0), clamped at 0 to drop negative branches.
Update best = max(best, node.val + left_gain + right_gain) — the path that uses both branches through this node.
Return node.val + max(left_gain, right_gain) as the best single branch this node offers its parent; call gain(root) once and return best.
Complexity
Time: O(n) — Space: O(h)
Code
def maxPathSum(root: TreeNode | None) -> int:
best = float("-inf")
def gain(node: TreeNode | None) -> int:
nonlocal best
if not node:
return 0
left_gain = max(gain(node.left), 0)
right_gain = max(gain(node.right), 0)
best = max(best, node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)
gain(root)
return best
Code Explanation
How the solution above works, piece by piece.
gain(node) returns the best sum of a path that starts at node and goes down one side.
max(gain(child), 0): a negative branch is dropped rather than added.
node.val + left_gain + right_gain is the best path that bends at this node; update best.
Return node.val + max(left_gain, right_gain): a path continuing to the parent can use only one child.
best starts at −∞ so trees with only negative values work. O(n) time, O(height) stack.
Visual Walkthrough
Running it on root = [-10, 9, 20, null, null, 15, 7]:
Under each node is the gain it reports upward: its value plus its better child (negative gains are replaced by 0). The best total uses both children at one node, here 15 + 20 + 7 = 42; including −10 would only lower it.