Binary Tree Maximum Path Sum

A path is any sequence of nodes where each pair of neighbours is connected by an edge, and no node appears twice. It does not have to pass through the root and can start and end anywhere, but it contains at least one node. Find the maximum possible sum of values along a path.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree (at least one node).

Output: the maximum path sum.

Constraints: 1 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: for each node compute the best "downward" path starting at it: val + max(0, bestDown(left), bestDown(right)). The best path that bends at this node is val + max(0, left) + max(0, right) — keep the global maximum. Careful with all-negative trees.