Binary Tree Maximum Path Sum

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear in a path at most once. The path does not need to pass through the root.

Given the root of a binary tree, return the maximum path sum of any non-empty path. A path sum is the sum of the node values along the path.

Note: Nodes can have negative values, so you must choose paths wisely — sometimes the best path is a single node.

Input / Output Format

Input: The root of a binary tree, represented as a level-order array where null indicates a missing node.

Output: A single integer representing the maximum path sum.

Examples

Example 1

    1
   / \
  2   3

Input: [1, 2, 3]
Output: 6
Explanation: The optimal path is 2 → 1 → 3 with sum 2 + 1 + 3 = 6.

Example 2

       -10
       /  \
      9   20
         /  \
        15   7

Input: [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation: The optimal path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42. Note that the root (-10) is excluded because it would reduce the total.

Example 3

  -3

Input: [-3]
Output: -3
Explanation: With only one node, the best path is the node itself.

Approach Hints

1. Think recursively: For each node, consider what the best path looks like if it passes through that node as the "peak" (highest point in the path).

2. Each node contributes: When extending a path upward to a parent, a node can only contribute its value plus one of its child branches (left or right) — not both. However, when a node is the peak, it can connect both its left and right branches.

3. Track a global maximum: Use a variable (or reference) to keep track of the best path sum seen so far across all recursive calls.

4. Handle negatives carefully: If a child subtree yields a negative contribution, it's better to ignore it (treat it as 0) when extending upward.

5. Time Complexity: An optimal solution visits each node exactly once — aim for .