You can refer to the Leetcode problem 124. Binary Tree Maximum Path Sum
In my personal opinion, this question has the ability to judge your analytical and tree traversal skills. You must give it a try before jumping onto solution.
By that you might get to know how ruthless this problem is. At the end of this article you would develop the thinking capability and would be able to solve problems likepathsum
,longestbranch
,diameter of a tree
etc. See related problems at the end. Cheers!
Problem Statement
Given the root
of a Binary Tree
, return the maximum path sum
of any nonempty path
.
A path
in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once
. Note that the path does not need to pass through the root.
The
path sum
of apath
is the sum of the node's values in the path.
Example 1:
Input:
root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 > 1 > 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input:
root = [10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 > 20 > 7 with a path sum of 15 + 20 + 7 = 42.
Intuition
We first need to carefully understand the problem statement and note out some key points.

Path
: In first attempt it would sound like usual root to leaf path, but that's abranch
for any given root. Apath
in general is a chain of 1 or more adjacent(connected and contiguous) nodes. It, the path, may or may not includeroot
itself. That's the essence of the question that it's asking for any path that gives us maximum sum(when values added). 
NonEmpty Path
: This makes sense as we are not going to count a nil path. 
At most once
: This must be taken into account that a valid path must not include a node more than once.
Now since we are clear that a path with maxsum may exist without the root itself, it means for whatever algo we deduce, we need to visit each node in recursion. May be our max path would be lying somewhere down. See below examples to make it more clear.
Although there several path that are possible out of these 5 nodes or 4 edges. Let's list them down:
Starting at node 2:
 2 : sum = 2
 2 <> 3 : sum= 1
 2 <> 3 <> 3 : sum = 2
 2 <> 3 <> 3 <> 4 : sum = 6
 2 <> 3 <> 3 <> 5 : sum = 7
Starting at node 3:
 3 : sum = 3
 3 <> 3 : sum = 0
 3 <> 3 <> 4 : sum = 4
 3 <> 3 <> 5 : sum = 5
Starting at node 3:
 3 : sum = 3
 3 <> 4 : sum = 7
 3 <> 5 : sum = 8
Starting at node 4:
 4 : sum = 4
 4 <> 3 <> 5 : sum = 12
Starting at node 5:
 5 : sum = 5
Note that the a path order does not matter while calculating the sum, so a path 3 > 4
will be same as 4 >3
Does it make any sense to return the max sum for path like 2 <> 3 <> 3
with sum as 2?
No! it's obvious that the output would be 12 for path 4 <> 3 <> 5
, see nodes highlighted in green.
Let now try to build our logic now. We shall taking into consideration each obvious permutations.
1. No left/right subtree (Single node tree or a leaf node)
If you ever get your hands dirty with tree traversal, you might have encountered the situation where curr is pointing to leftmost node or any leaf node.
We used to put this node onto stack (as it's not null) and after this, our curr would be pointing to it's left or right as per the order.
Remember, single node is also a valid path!
Now for pathsum, since we do not have anything as it's left or right, we would be returning the node value directly.
What if the left and right child exists? In that case we shall evaluate if that's profitable or not?
2. When subtree exists (Evaluating the Gain/Profit)
Before going to logic, can you tell us if we shall take 1
& 2
into account to get a max sum ? No! Why should we, because we are good with only node 1
.
Adding 1 or 2 into the path would further decrease our max value, that's something like profit and loss. So how shall we program this logic?
What about this one?
Shall we add the node 3
now? In previous diagram, our maxsum was 1. In this, if we take the new node 3
, our max sum becomes 2.
So our new path becomes 1 > 2 > 3
that results in a max sum of 2.
To add to your surprise, we are wrong here! That's something that we need to take care.
We would not be taking the path from node 1
to 3
. If you look closely, only node 3
alone is making a greater max.
path 1 > 2 > 3
is less profitable as compared to path 3
only.
We can deduce some key points here:

We need to get maximum sum for left child and right child. Let's create a function
someMethodToGetMaximumSumFromTreeNode
that would accept aTreeNode
.int leftMax = someMethodToGetMaximumSumFromTreeNode(curr.left)
int rightMax = someMethodToGetMaximumSumFromTreeNode(curr.right)
If there are other branches to visit, we can not take both left and right or in other words we can not have 3 way path.
So we should choose a maximum out of these leftmax or rightmax and combine this path with parent to get a path. Let's call itmaxChildren
int maxChildren = Math.max(leftMax, rightMax)

We need to check if adding left or right(whichever way is greater) to current would increase or path sum or decrease. How to do this? We need to use
Math.max()
function with left and right.int maxWithRoot = Math.max(curr.val, (curr.val + maxChildren))

We also need to check if left and right together along with root form a greater value or not ? This is something adding all the nodes if a tree
[1,2,3]
.
Let's call thismaxNode
.int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax)

Last part for calculating the max sum is if already found a greater path sum or is this a new greater sum. We need to update our answer accordingly.
maxSum = Math.max(maxSum, maxNode)
So that was all about evaluating the profitability and assigining bigger max to our answer.
But we have not worked on the return type and it's logic for function someMethodToGetMaximumSumFromTreeNode
.
This function, for each tree node, evaluates the maximum path sum uptill(root must be included in path sum) the given root.
So for a tree [1, 2, 3]
, leftMax would be 2
and right max would be 3
and the return value would be maximum of 2
& 3
+ root value.
Do we already have such logic? Yes! See maxWithRoot
and this is what we would return in our function.
Note that, we are evaluating our answer in variable
maxSum
whereas the return value for the function is returned bymaxWithRoot
Complexity Analysis
Time complexity
: O(N)
, where N
is number of nodes, since we visit each node not more than 2 times.
Space complexity
: O(H)
, where H
is a tree height, to keep the recursion stack. In the average case of balanced tree, the tree height H = logN, in the worst case of skewed tree, H=N.
program
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
//recurse(root);
getMaxPathSum(root);
return maxSum;
}
int recurse(TreeNode root){
if(root == null) return 0;
int leftMax = recurse(root.left);
int rightMax = recurse(root.right);
int maxChildren = Math.max(leftMax, rightMax);
int maxWithRoot = Math.max(root.val, (root.val + maxChildren));
int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax);
maxSum = Math.max(maxSum, maxNode);
return maxWithRoot;
}
// Enhanced version of our logic
private int getMaxPathSum(TreeNode root) {
if (root == null) return 0;
int leftMax = Math.max(0, getMaxPathSum(root.left)); // Take 0 instead of a negative left sum
int rightMax = Math.max(0, getMaxPathSum(root.right)); // Take 0 instead of a negative right sum
maxSum = Math.max(maxSum, (leftMax + rightMax + root.val));
return Math.max(leftMax, rightMax) + root.val;
}
}
Test cases
For this particular I have pled up few edge cases that you should try before submitting your soltution
[1]
[1]
[1,null, 1]
[2, 1]
[2, 1, 2]
[1,2,3]
[1,2,3,1,3,2,null,1]
[3,9,20,null,null,15,7]
[1,2,3,1,3,2,null,1]
[10,9,20,null,null,15,7]
[1,2,3,null, null,4,5,6,7,8,9,10]
[5,4,8,11,null,13,4,7,2,null,null,null,1]
[1,2,3,null, null, 4,5,6,7, null,8,9, null, 10, 11, null, null,12, 13, 14, null, 15, null,16, null, null, 17, null, null, 18, null]
[1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 1,null, 16]
Related problems
 Path Sum
 Sum Root to Leaf Numbers
 Path Sum IV
 Longest Univalue Path
 Time Needed to Inform All Employees
 Diameter of Binary Tree
Problem Credit : leetcode.com
Top comments (1)