The machine must find the maximum sum of any path in the tree, where a path is any connected chain of nodes that never revisits a node. The path can start and end anywhere and is allowed to dip into negative values.
The key insight is that a path through a node either stays entirely inside one subtree or passes through the node, joining one branch from the left with one branch from the right. That means the recursion must compute two things: the best downward path starting at the node (returned upward) and the best path passing through the node (tracked in a global answer).
The approach has three steps. First, recurse post-order to get the best downward path from each child, clamping any negative branch to 0 because a path is free to stop before a loss-making subtree. Second, compute the through-path value as the node's value plus both clamped branches, and update the global maximum with it. Third, return the node's value plus the larger of the two branches — that is the only upward contribution a parent can use. Each node is visited once, so time is O(n) and space is O(h).
The trickiest edge case is an all-negative tree: clamping branches to 0 would produce 0, but the machine must report the largest single negative value. Initializing the global answer to negative infinity, not 0, and letting the through-path check run at every node handles this correctly.
def maxPathSum(root):
best = float('-inf')
def dfs(node):
nonlocal best
if not node:
return 0
left = max(dfs(node.left), 0)
right = max(dfs(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
dfs(root)
return best