Simple tree with positive values
Input
Tree: 1 / \ 2 3
Output
6
The best path is 2 -> 1 -> 3 with sum 2 + 1 + 3 = 6.
Full lesson preview
Find the maximum path sum in a binary tree
Compute the maximum sum obtainable by any path in a binary tree (path may start and end at any nodes).
Python practice25 minTrees & Binary TreesAdvancedLast updated March 29, 2026
Problem statement
Given the root of a binary tree where each node contains an integer (which may be negative), return the maximum path sum. A path is any sequence of nodes connected by edges, where each consecutive pair in the sequence has a parent-child relationship. The path may start and end at any nodes in the tree and must contain at least one node. Your function should return the maximum possible sum of values along such a path.
You must handle negative values correctly: if all values are negative, the maximum path is the single node with the largest (least negative) value.
Task
Implement an algorithm to find the maximum path sum in a binary tree. The path must contain at least one node and can go through parent-child links; it does not have to pass through the root.
Examples
Input format
A binary tree constructed using the provided TreeNode class. Call max_path_sum(root) with the tree root.
Output format
An integer representing the maximum path sum.
Constraints
The number of nodes in the tree is in the range [1, 3*10^4]. Node values are integers in the range [-10^4, 10^4]. The solution should run in O(n) time using O(h) recursion stack where h is the tree height.
Samples
Sample 1
Input
Tree: [ -10, 9, 20, null, null, 15, 7 ]
Output
42
The maximum path is 15 -> 20 -> 7 = 42 (through node 20).