Binary Tree Maximum Path Sum

A parent can extend only one branch from a child, but the globally best path may use both branches through a node. Keep these two quantities separate.

Run a postorder DFS. Let left = max(0, dfs(node.left)) and right = max(0, dfs(node.right)). Negative gains are discarded because adding them can only reduce a path. The best complete path whose highest point is this node is node.value + left + right; use it to update a global maximum. Return node.value + max(left, right) to the parent because a path extended upward cannot fork into both children.

Initialize the global maximum to negative infinity, not zero. That ensures an all-negative tree returns its largest single node rather than an invalid empty path.

Every node is visited once, so time is O(n). Recursive stack space is O(h), where h is tree height. The correctness hinge is that every simple path has one highest node, and the global update evaluates the best path for each possible highest node.