Maximum Path Sum in a Binary Tree

Postorder recurrence

For each node, compute the best sum of a path that starts at that node and can be extended to its parent. A parent can extend through only one child, so return node.val + max(0, leftDown, rightDown). Separately, the best complete path whose highest point is this node may use both children: node.val + max(0,leftDown) + max(0,rightDown). Update a global answer with that value on every visit.

Correctness and edges

Postorder guarantees both child contributions are available before processing a node. Clamping a negative contribution to zero is safe because starting a new path at the node is better. Initialize the global answer to negative infinity, not zero, so an all-negative tree works. Do not return the two-branch value: that would create an invalid fork when a parent tries to extend it. Time is O(n) because each node is visited once; recursion-stack space is O(h), where h is tree height.