Binary Tree Maximum Total Path

You're given the root of a binary tree whose nodes hold numbers — some positive, some negative. A path is any sequence of nodes connected by parent-child edges; it does not have to start at the root, and it does not have to end at a leaf. Each node appears at most once. Return the largest possible sum of node values along any such path.

The catch is the shape of "any path." A path can be a single node, a chain down one side of the tree, or it can pivot at a node — descending into the left subtree, passing through the pivot, and ascending into the right subtree. Once you turn, you can't turn again, because turning twice would re-visit an ancestor.

Signature

type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null };

function maxPathSum(root: TreeNode | null): number;

Return -Infinity when root is null (no path exists).

Examples

// Linear positive chain — the whole chain wins.
//   1 -> 2 -> 3
maxPathSum({ value: 1, left: null, right: { value: 2, left: null, right: { value: 3, left: null, right: null } } });
// → 6

// Single negative node — the only available path is "use this node."
maxPathSum({ value: -3, left: null, right: null });
// → -3

// Mixed signs — skip the negative subtree, take just the positive side.
//          5
//         / \
//     -100   3
maxPathSum({ value: 5, left: { value: -100, left: null, right: null }, right: { value: 3, left: null, right: null } });
// → 8

// Inverted-V wins — best path turns at the root.
//      10
//     /  \
//    5    7
//   /
//  1
// → 23  (path 1 -> 5 -> 10 -> 7)

Notes

• Path length is at least one. You cannot return 0 by claiming the empty path; on an all-negative tree the answer is the single least-negative node.
• At most one turn per path. Every path is shaped like a chain or an inverted V — descend, optionally pivot once, ascend on the other side.
• Negative values are real. Longer paths can be worse than shorter ones. The right move is sometimes to skip an entire subtree because everything in it lowers the sum.
• Don't mutate the tree. The input tree should look identical before and after the call.
• Null root convention. Return -Infinity when the root is null. There is no path through an empty tree, so we signal that with a sentinel rather than returning 0 (which would be wrong on all-negative trees).