Binary Tree Maximum Path Sum
Given the root of a binary tree, find the maximum path sum.
A path is a sequence of nodes where:
- Each pair of adjacent nodes is connected by an edge.
- A node can appear at most once.
- The path does not have to pass through the root.
- The path can start and end at any two nodes.
Example
-10
/ \
9 20
/ \
15 7
The maximum-sum path is:
15 → 20 → 7
So the answer is:
42
because:
15 + 20 + 7 = 42
Example 1
Input
root = [-10,9,20,null,null,15,7]
Output
42
Explanation
The tree is:
-10
/ \
9 20
/ \
15 7
The best path is:
15 → 20 → 7
Its sum is:
15 + 20 + 7 = 42
The path does not need to include the root -10.
Example 2
Input
root = [1,2,3]
Output
6
Explanation
The tree is:
1
/ \
2 3
The maximum path is:
2 → 1 → 3
Therefore:
2 + 1 + 3 = 6
Constraints
Hints:
Hint 1
For every node, calculate the maximum path sum that can be extended upward to its parent.
Hint 2
A node can receive a contribution from its left and right children.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 13, 2026
Last updated
Aug 14, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output