Find the maximum sum of any path in a binary tree, where the path can start and end at any nodes but must follow parent-child links.
Binary Tree Maximum Path Sum
Given the root of a binary tree, find the maximum possible sum of values along any non-empty path in the tree.
A path is a sequence of nodes connected by edges where each adjacent pair is directly connected by a parent-child link. The path does not need to pass through the root, and it may start and end at any two nodes. Each node can appear at most once in the path.
The path must contain at least one node.
Your task is to return the largest path sum that can be formed in the tree.
Input Format
- A binary tree root node.
- Each node contains an integer value.
- The tree structure is given in the usual node/left/right form used by the platform.
Output Format
- Return a single integer: the maximum path sum among all valid paths in the tree.
Constraints
- The path must be non-empty.
- Values may be negative, positive, or zero.
- The tree can contain only one node.
- The answer should fit in a 32-bit signed integer for typical interview constraints.
Example 1
Input
root = [1,2,3]
Output
6
Explanation
The best path is 2 -> 1 -> 3, with sum 6.
Example 2
Input
root = [-10,9,20,null,null,15,7]
Output
42
Explanation
The best path is 15 -> 20 -> 7, with sum 42.
Show 1 more example
Example 3
Input
root = [-3]
Output
-3
Explanation
With a single node, the only path is the node itself.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.