Binary tree maximum path sum | Leetcode

This video explains a very important interview programming question which is to find the maximum path sum in a binary tree. This is a very important binary tree question and the problem is very similar to finding diameter of a binary tree. I have explained the intuition for solving this problem including all the cases to be handled. I have explained the code flow with proper examples and code explanation is present at the end of the video.As usual, CODE LINK is present in the description below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
Similar Problem:
Diameter of a binary tree: • Diameter of a binary t...

[@shubhiagarwal4047]

Sir , this explanation deserves much more applaud , that's why I shared your channel to all my juniors.

[@yimingzhao3753]

Seen a few explanations on UA-cam, this is the best one so far, way to go!

[@techdose4u]

:)

[@ayaramzy6815]

@@techdose4u yea the best one

[@uwontlikeit]

1:09 - EXAMPLE 2 IS INCORRECT. max sum = 6 (not 5) and includes the root, and the rightest node

[@jagdishwarbiradar1763]

Well explained with example 🍁 , Smart way by using the three cases it clear all my doubts 👍🏻.

[@techdose4u]

Thanks man :)

[@ssss-jd9cl]

can anyone explain why m21 has taken value max of ms and left+right+root->data. we can take only some value of left+right+node also. I am getting confused in this. Anyone explain.

[@saharshrathi7828]

Such a great explanation! I just watched the video to understand the algorithm and you explained it so good! Then coded the algorithm by myself and the solution got accepted in the first try! Subscribed.

[@techdose4u]

Thanks :)

[@punittiwari7557]

The example which you have illustrated where the sum was 5, the maximum sum we can achieve is 3->2->(-1) ->2 sum=6

[@dumbcurious450]

Probably the best explanation of this problem on You Tube .. Thanks Man

[@techdose4u]

Welcome :)

[@babumon5351]

Really good explanation. I started to understand the logic when with a playback speed of .75. Thanks

[@techdose4u]

Nice :)

[@lemax2980]

Respect for the effort! 🙃.
Thank you for the great content and please , if you are comfortable,teach us about graphs after the leetcode saga😅

[@sankarikarthick801]

This is the best explanation I have come across for this question.

[@techdose4u]

Thanks :)

[@DMDRPBHU]

he saves results as max which would o/p the max sum
but doest return the result since the left or right side of the tress must be a straight iine and not a sub tree

[@sangramkapre]

Nice! The only explanation I understood on UA-cam :-)

[@techdose4u]

:)

[@m.praneethreddy7335]

Best channel in the youtube for data structures and algorithms👌👌

[@raviagarwal4287]

The way in which you explained this complex problem is lit💥
Keep it up👍

[@techdose4u]

Thanks :)

[@mikasaackerman2694]

Nice explanation!! The solution felt really intuitive after looking at this video

[@techdose4u]

Thanks

[@mohitshoww]

No one Can Explain Like You .

[@techdose4u]

😁 Thanks

[@deepanshu6576]

worlds best video ,sir aur bnayo aisi interview bit se lekr ,clear all the doubts

[@techdose4u]

Thanks

[@jlecampana]

Great Video, best explanation available. To me the tricky part was to understand why m21 needs to be a max(ms, left + right + root->val) and not just: left + right + root->val. Could you maybe elaborate on that. Thank you!

[@techdose4u]

Thanks. Because there might be a max sum path in either left or right subtree which is not rooted at current node.

[@tarunsingh3687]

Damn!! It was leetcode HARD I understood at one go. Kudos to you ! You provide quality content. Keep making videos and thank you so much.

[@techdose4u]

Welcome :)

[@divyamgupta2100]

Can you explain why only case 1 is returned, only that part is confusing me.

[@utkarshgupta6258]

By far the best explanation

[@factsclub4u]

@Techdose just one doubt i had why we are returning case 1 value only and hence returning max_straight .Please give clear explaination.

[@aneeshsharma]

Very good explanation of the Cases. Thank You !

[@techdose4u]

Welcome bro :)

[@koyavasudhalakshmi2073]

Sir ,could u please provide the link for inserting nodes into binary tree dynamically at what ever place we want,
But in generally I found inserting via level order in binary tree.

[@madhavsahi7400]

at 1.46 in the second tree example why u havent consider -1 , 2 in ur path ?? the maxsum will be 6 which is greater than 5 as in ur selected path

[@techdose4u]

Yes you are correct. Actually I wanted it to be -2 but it turned out to be 2. My bad. Consider that -2.

[@madhavsahi7400]

@@techdose4u okay sir thanks

[@techdose4u]

Thanks for pointing out :)

[@madhavsahi7400]

@@techdose4u one doubt sir...I also solve problems in C++ ...and I wanted to ask what those code statements at line 29,30 mean ?...

[@harshagarwal2629]

Supppppppperrrrbbbbb explanation....U just made a hard problem look so easier . Explanation is awesome :)

[@techdose4u]

Thanks

[@mrshubh101]

Excellent explanation! I understood this in the first go. I'm now curious to know, since every recursive approach also has an iterative approach, how will this problem be solved iteratively, without recursion? Also, since we've kept track of the max sum, can we also extend this problem to return a list of nodes which are part of max sum path? Like in the above example, max sum = 18, nodes = [8->4->1->5]

[@julietgeorge4858]

Thank you for showing/explaining the algorithm before the code. I use javascript and so it is helpful.

[@yashikagarg4044]

Please make video on path sum question where we have to check if path with given sum exists on leet code

[@techdose4u]

Maybe I will take this when I do TREE.

[@sarahzaman3173]

thank you, this was the best explanation I could find.

[@techdose4u]

Welcome 😊

[@Neerajkumar-xl9kx]

can't be explained better than this...thank you

[@techdose4u]

Welcome :)

[@aadhavan-arunkumar]

Amazing explanation!. Do you mind sharing where do you work?

[@techdose4u]

Currently I am teaching students and working professionals and guiding them to get better opportunities :) Follow me on LinkedIn to know more

[@LaxmiNarayana-zs5vz]

Thanks for the great explanation!.
how to actually store the path and print the nodes involved in our maximum path?

[@aryamarda1643]

I was able to do it by your bt diameter ques. Explanation.
Thank you 😀

[@nickscriv5141]

Why is it traversing to every node 3 times? It looks like the traversal just visits each node once.

[@techdose4u]

Going to child and then coming back and again going to another child. It's technically 1 visit but recursion makes it 3 times if you consider going from child to parent as a visite :)

[@x12624]

Why are we returning the case1 value at the end instead of the result?

[@harishkumarreddy079]

very good explanation for a hard problem

[@dimplerohara3799]

Best explanation so far!

[@techdose4u]

Thanks :)

[@viralmehta2542]

very nicely explained in detailed.

[@salonikaur7043]

Why do we return case 1 in the helper function?

[@hiteshgupta7652]

Amazing Explanation Sir, Looking forward to more hard questions like these!

[@techdose4u]

They will come in may challenge :)

[@biswaMastAadmi]

excellent explanation ! keep going !

[@techdose4u]

Thanks ☺️

[@competitivedoritos4294]

i searched tons of resource but couldn't understand this problem, thank you so much sir for this video :)

[@techdose4u]

Welcome :)

[@sakibmalik1613]

So beautiful, I done it the hard way it got AC anyway, I was unsure of what to return to the parent LOL

[@techdose4u]

😅

[@arnavkarforma3015]

I liked your solution on diameter of a trees, and it seemed to me jus same question with one difference that here there were negative values. Just because I was familiar with that approach used that
class Solution {
public int maxPathSum(TreeNode root) {
return maxPathSumRec(root)[1];
}
int[] maxPathSumRec(TreeNode root){
int largestSum = -99999;
if(root == null){
return new int[]{0,largestSum};
}
int[] left = maxPathSumRec(root.left);
int[] right = maxPathSumRec(root.right);
left[0] = Math.max(left[0], 0);
right[0] = Math.max(right[0], 0);
largestSum = Math.max((left[0] + right[0] + root.val), Math.max(left[1],right[1]));
return new int[]{Math.max(left[0],right[0])+root.val,largestSum};
}
}

[@techdose4u]

👍

[@anujasrivastava3446]

This is a really nice explanation! Thank you!

[@techdose4u]

Welcome :)

[@PriyankaSharma02499]

Very nice explanation

[@techdose4u]

Thanks

[@varunnadipudi2257]

Well done!!Explanation is very nice.

[@techdose4u]

Thanks

[@gautamgoel2024]

This is a hard problem to understand but sir you made it easy❤️

[@techdose4u]

👍🏼

[@gautamgoel2024]

@@techdose4u sir can we have a video on🙏 print all ''k"" sum paths in a Binary tree🙏

[@RajatSingh-dg8ov]

why can we only return max straight value?. You did not explain that. If there's no use of doing maxCaseVal and result, since they are not getting returned, even max_straight is not even updated anywhere after line 21. Why not return that directly?.

[@vaibhavjain4710]

Best explanation , I have ever seen ;)

[@techdose4u]

Thanks :)

[@deviprajwala9779]

Amazing explanation!!

[@techdose4u]

Thanks

[@markos8955]

Nice Explanation........Nice to see having no Dislikes.

[@techdose4u]

Thanks :)

[@InderjeetSingh-no3pp]

Nice explanation.....easily understandable

[@techdose4u]

Thanks :)

[@aashishkalia8269]

You explain really nice and simple !!

[@techdose4u]

Thanks :)

[@harshagarwal2629]

Hey, please make a video on sum of distances in a tree question from leetcode .

[@techdose4u]

Will try

[@rocknroll7967]

How to come up with this solution in interview if we have not seen this problem before?

[@techdose4u]

You must have seen this problem. This is one the most common tree problem. There can be multiple variations of this. If you have solved only 1 of them then you can get the idea.

[@rocknroll7967]

@@techdose4u I learnt this the hard way. Thanks for the awesome video

[@midhileshmomidi3120]

Why are we returning max-straight? why we can't we return result. I didn't get this

[@MagicalCreationAviCreation]

Sir in
112. Path Sum(Leetcode problem)
Sir consider one case when my sum is lesser than the zero (after reaches of some node).
and however we know my solution is not in this sub tree, i am simply continuing recursion tiil i reaches leaf node.
sir is there any solution to this .......
[5,4,8,11,null,13,4,7,2,null,null,null,1,3,4]
sum == 22
here after i reaches the node 7 , here i get know this is not the best path,however i am continuing recursion of leaf node 3 and 4
sir if i break the recursion at node 7 we can reduce time complexity am i right sir......

[@mansibhardwaj3976]

Excellently explained!!

[@techdose4u]

Thanks

[@chhaviagarwal7514]

very well explained.. Thanks

[@techdose4u]

Welcome

[@OGIL-ir3rp]

**** JAVA VERSION OF THE ABOVE APPROACH ******
class MyInt {
int result = Integer.MIN_VALUE;
}
public int maxPathSum(TreeNode root) {
MyInt myint = new MyInt();
maxPathSumHelper( root, myint );
return myint.result;
}
public int maxPathSumHelper(TreeNode root, MyInt myint){
if( root == null ) return 0;
int leftSum = maxPathSumHelper( root.left, myint );
int rightSum = maxPathSumHelper( root.right, myint );
int maximumSum = Math.max( Math.max( leftSum, rightSum) + root.val, root.val );
int maxSumAcross = Math.max( maximumSum, leftSum + root.val + rightSum );
myint.result = Math.max( maxSumAcross, myint.result );
return maximumSum;
}

[@techdose4u]

👍

[@priyanshukhullar5836]

great explanation

[@techdose4u]

Thanks :)

[@gaminghub305]

Java Code Hope it helps!
class Solution {
static int result=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root)
{
if(root==null) return 0;
Max_finder(root);
return result;
}
private static int Max_finder(TreeNode root)
{
if(root==null) return 0;
//going down to leaf node and will start calculating from there.
int left=Max_finder(root.left);
int right=Max_finder(root.right);
// calculating while backtracking.
int Straight_path=Math.max(Math.max(left,right)+root.val,root.val);
int all_Maxval=Math.max(Straight_path,left+right+root.val);
result=Math.max(all_Maxval,result);
return Straight_path;
}
}

[@anuragsinha5928]

Java Solution
-----------------------
class Solution {
int sum=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null)
return 0;
height(root);
return sum;
}
public int height(TreeNode root){
if(root==null)
return 0;
int leftS=height(root.left);
int rightS=height(root.right);
int ms=Math.max(Math.max(leftS,rightS)+root.val,root.val);
int ms12=Math.max(ms,root.val+leftS+rightS);
sum=Math.max(sum,ms12);
return ms;
}
}

[@techdose4u]

Thanks for sharing

[@aniketsriwastva6345]

Great Explaination Sir

[@techdose4u]

Thanks

[@neerajpandey8159]

Why we are return max_ straight instead of result.🤔🤔🤔

[@ayushthakur733]

Amazing explanation 👌

[@techdose4u]

Thanks 😀

[@samkitjain2136]

bhai aap legend ho yaar

[@sankarikarthick801]

Same solution in java:
public class BinaryTreeMaxPathSum {
int max_seen_until_now=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPath(root);
return max_seen_until_now;
}
public int maxPath(TreeNode root) {
if(root==null){
return 0;
}
int left=maxPath(root.left);
int right=maxPath(root.right);
int max_straight_path=Math.max(Math.max(left,right)+root.val,root.val);
int max_curr_node_as_root=Math.max(max_straight_path,left+right+root.val);
max_seen_until_now=Math.max(max_curr_node_as_root,max_seen_until_now);
return max_straight_path;
}

[@techdose4u]

👍

[@pratyush2604]

Amazing explanation! Thanks a lot

[@techdose4u]

Welcome :)

[@recklessekta]

very well explained, thanks!

[@techdose4u]

Welcome :)

[@shivamsingh7219]

Why you returning max_straight in recursion function.

[@shivamsingh7219]

I got it bcz we want left and right value of curr node that's why returning max_straight

[@programmingstuff5741]

These are also such questions to prepare for. Interviews

[@PhoenixRisingFromAshes471]

outstanding solution brother

[@techdose4u]

Thanks bro :)

[@bhairavas2528]

Can you please mention TC and SC for this approach??

[@shubhambhandari431]

how much time and practice needs to solve problems like this?
n how to do?

[@afnaanrafique366]

java implementation not passing all test cases on leetcode

[@sanky52]

for input -9 6 -10 output is 6 but expected output is -13 in gfg

[@chetanpatteparapu7600]

Thank you very much Mate. Very nice explanation

[@techdose4u]

Welcome :)

[@tanmayagupta4591]

Thanks!

[@techdose4u]

Welcome :)

[@dhawaldhingra]

In 2nd example stating at 1:00 minute, the maximum path of the tree should be 6 and not 5. The max path still goes through the root. It goes like- 3->2->-1->2 :)

[@RahulKumar-wv4ti]

Thanks bro

[@techdose4u]

Welcome

[@usrivastava92]

brilliant explanation.. thanks alot.. :)

[@techdose4u]

Welcome :)

[@ketanahuja8939]

Wonderful

[@techdose4u]

:)

[@yuhaokong]

ok this explanation is pretty damn clear

[@techdose4u]

Thanks :)

[@mohamedmusaraf675]

Thanks a lot.!!

[@kartikwar8022]

python solution
class Solution:
def maxPathSum(self, root) :
self.ans = -float('inf')
def traverse_path(root):
if not root:
return 0
left = max(traverse_path(root.left),0)
right = max(traverse_path(root.right),0)
val = root.val
self.ans = max(self.ans,val+left+right)
return val+max(left,right)
traverse_path(root)
return self.ans

[@ashutoshshukla5253]

why we returning max_s instead result???

[@techdose4u]

I have explained this clearly. We are returning MS (case-1) value only because result is keeping track of max path sum found so far. It may or may not include the current node. Also, result is passed by reference and hence latest changes are available at places. No need to return result. The only thing we want to return is MS because we want to check if we can find some other path which will have more path sum as compared to current maximum stored in result.

[@ashutoshshukla5253]

got the solution keep uploading more videos it help our coding skills

[@willturner3440]

Thanks bhai

[@techdose4u]

Welcome

[@sakibmalik1613]

Here's mine
int maxi(int a, int b, int c){
return max(max(a, b), c);// max of 3 no(s)
}
int helper(TreeNode* root){
// if at leaf check if positive and add
if(!root->left && !root->right)return max(root->val, 0);
int left = INT_MIN;
int right = INT_MIN;
if(root->left)left = helper(root->left); // should left side be chosen ?
if(root->right)right = helper(root->right); // should right side be chosen ?
return max(max(left, right) + root->val, 0); // max of both side + the value is > 0 or not ?
}
int cross(TreeNode* root){
int x = 0, y = 0;
if(root->right) x = helper(root->right); // should right side be added or not ?
if(root->left) y = helper(root->left); // should left side be added or not ?
return root-> val + x + y; // path through root (sum)
}
int maxPathSum(TreeNode* root) {
// if single node return it
if(!root->left && !root->right)return root->val;
int left = INT_MIN; // max path sum (completely left side)
int right = INT_MIN; // max path sum (completely right side)
if(root->left)left = maxPathSum(root->left);
if(root->right)right = maxPathSum(root->right);
int through = cross(root); // max path sum passing necessary through root
return maxi(left, right, through); // max of all is the ans
}

[@techdose4u]

Looks messy 😅

[@sakibmalik1613]

@@techdose4u yeah youtube doesn't support code yet ig

[@humansofcrypto9746]

Excellent!

[@techdose4u]

Thanks :)

[@evgeni-nabokov]

The solution is overcomplicated. The problem similar to the problem of the diameter of the binary tree. Just a little change in formula for left and right values. In this case, we have to compare left and right values to 0 to disregard negative sums of branches.

[@techdose4u]

You can directly copy the the code of diamter of a binary tree by just changing the objective and it will work. I dint think this was complicated 😅 If you compare only left and right then what about case 3 values? How will you handle that?

[@evgeni-nabokov]

@@techdose4u There is only one case -- the node is the root of the path. The path can be a single node, the path can be a root node with a single branch, or regular path.

[@evgeni-nabokov]

@@techdose4u gist.github.com/evgeni-nabokov/d67d098aea95e48e20bb0c219983257d

[@HiBMlive]

not working in java. passes 29/93 cases

[@techdose4u]

There must be some logical error or some minor implementation glitch with your java code. Please review and compare carefully.

[@chaunguyen8202]

Thank you!

[@techdose4u]

Welcome

[@cipherCrafters14]

Sir please help me i m math teacher in school i want to make online video on youtube please tell me which digital board you use sir please sir

[@techdose4u]

Ping me on LinkedIn.

[@yashgoswami5374]

good explanation sir

[@adityadhikle9473]

0.43 example 2 : Max sum is 6 not 5.

[@bhargavsai2449]

super hard to come up in the interview

[@emilyhuang2759]

@14:05, the Result is returned, but int the code, why can you only return max_straight and not the result?

[@varsha9094]

Yes , even I have the same question , 18 is stored in result and if we return ms don't we get 12 instead??