L17. Maximum Path Sum in Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@yashverma4938]

Bhai kitni mehnat kroge yr smjh nhi aarha yr 17 videos daldi ab tak trees pe yr insan ho ptani hulk ho bhai tumhe bhagwan sab kuch de yr jo tumhe chahiye meri dua h bhagwan se

[@arnabkundu8749]

Why did you take array in java for max ? Can you explain ?

[@kushagrasaxena2115]

Bhaiya what if the tree is like -9 as root node and left node as 6 and right as -10 , then the output should be -13 because we have to consider at least one path that in this case would be 6+(-9)+(-10)= -13 but with your code the output will be 6 ... Please help me understand this .... i am a bit confused right now .... or have not understood the question well enough...

[@bhaveshkumar6842]

​@@arnabkundu8749 Buddy, KEEP THE CODE IN FRONT OF YOU and then read this. We can't return the max value in the recursive function since we are returning "Math.max(left, right) + node.val" to the variables "left" and "right" in the recursive function "int left = Math.max(0, maxPathDown(node.left, maxValue))" and "int right = Math.max(0, maxPathDown(node.right, maxValue))". So we store the max value in an int array of size 1 (maxValue[ ] is of size 1) (which will store one value just like an int) and the final value of maxValue[0] can be accessed in the function "public int maxPathSum(TreeNode root)". If we had used an int variable like int maxValue (and not an array) and then called maxPathDown(root, maxValue) the recursive function maxPathDown(root, maxValue) would have created a local copy of int maxValue variable and maxValue in the original function won't have had access to the final value of the local copy variable which is calculated in the recursive function but if we use an array we can reference it in the original function (since an array is essentially pass by reference in Java. Java makes it pass by reference by passing the value of the address of the array)

[@hemantborse8923]

@@bhaveshkumar6842 thanks bro really helpful 👍

[@krishnasudan3410]

Height of the tree logic is working everywhere, what an explanation man.. hats off to your dedication.

[@parthsalat]

Thank you

[@ashrocks.9520]

even after 2 years this is the best dsa serires , the best part of it is thatt striver sir is never in a hurry to complete the topic , and this adds a taste to his way of explanation

[@keerthireddy8074]

When all the roots are negative, it gives the maximum value (minimum negative number) among all the children nodes.. It doesn't give 0.. I feel like it works for all negative case too where it considers only a single node rather than a 'path' connecting two nodes

[@divy04]

if leftsum or rightsum is negative , you can make them 0 as they will only reduce the sum, just like kadane algo

[@nikhilsinghjadon39]

literally, it doesn't feel like it's a hard question. such a great explantation it is.

[@mrpandey7312]

me: after watching every solution

[@prayagrajwade8699]

@@mrpandey7312 us bro us

[@vaibhavsingh4108]

@@mrpandey7312 us bro us

[@MayankSingh-ux9iz]

@@mrpandey7312 us moment bro

[@priyanshu1919]

@@MayankSingh-ux9iz us bro us

[@jayantmishra6897]

the best thing about you is you always bring the video in proper sequence that why toughest problem are looks like a easy problem.

[@jeet-smokey]

Never thought trees concept will be so easy, provided you get a teacher like Striver. Kudos...!!!!!

[@nitunsingh6986]

Awesome , U solved 3 questions (that are considered in hard category) just by small variation. Loving Tree Series. Although I already completed tree before

[@only_for_fun1234r]

Which 3 questions?

[@vempatisaivishal5426]

@@only_for_fun1234r1. height of tree 2.diameter of tree 3.checking tree is balanced or not

[@shivekagg25]

@@only_for_fun1234r height diameter and this question

[@aditi1729]

they're all marked easy on leetcode lol

[@muditkhanna8164]

@@shivekagg25 but they are not hard

[@aavashkuikel1341]

Thank you Striver! Height of tree logic works everywhere and everytime. Thanks a lot. Love from United States!

[@souradeepkar]

No body can explain recursion dry run like STRIVER!!!!!!!!!!!!!!!!!!!!!!!!! Thank you man!!!!!!!!!!!! YOU ARE A LEGEND :)))))))))))))))

[@lavanya_m01]

pre-req for this video is lec14 and lec 16 ( max-depth and diameter), he mistakenly said it as width. Anyways greatttt video, he made this leetcode hard question seem so simple. Gonna share this BEST playlist with all my frnds xD

[@pranavsharma7479]

diameter same as width

[@lavanya_m01]

@@pranavsharma7479 They're different, diameter is covered in lec16 and width in lec28. Go check

[@ok-jg9jb]

Hey you are cute

[@DhrutiSahoo]

The comment that is needed

[@swagatadas5121]

😂😂​@@ok-jg9jb

[@shreyansharora1320]

That is the most easiest approach i found, kudos to your work man. Appreciate that

[@shivangisrivastava1158]

Recursion is a topic i knew nothing of, but now i am becoming comfortable. Thanks to your rich content bhya! 🙌

[@pranav288]

what year are you in ?

[@lakshsinghania]

yeah, as tree is nothing but recursion

[@ananttyagi7372]

You are the best person to learn CP from, on YT.

[@sreejith5966]

Awesome very clear explanation My JS solution var maxPathSum = function(root) { let max = -Infinity; const solve = (curr)=>{ if(curr===null){ return 0; } let leftSum = solve(curr.left) ; let rightSum = solve(curr.right); leftSum = leftSum > 0 ? leftSum : 0; rightSum = rightSum > 0 ? rightSum : 0; max = Math.max(max,curr.val+leftSum+rightSum); return curr.val+Math.max(leftSum,rightSum); } solve(root); return max; };

[@audioeditsnstuff]

i don't think this problem could have been explained more beautifully than this :>

[@ritikshandilya7075]

The art of making hard question to easy one with excellent explanation and simplistic approach . Thanks for great solution striver

[@pranavmahendra3423]

Great explanation, sir. I loved how you solved this Binary Tree Maximum Path Sum question by using the concept that was used in Maximum Depth of Binary Tree and Diameter of Binary Tree. Thanks for all your efforts!

[@amanpreetsinghbawa1600]

Thanks for building the intuition in the previous tree height related vids, I was able to solve this one even without watching this. Striver the DSA guru

[@JayaSingh1063]

OP explanation!! So whenever I see any video of Striver, I always understand the concept in a very interesting and easiest manner.

[@harshgahlot2555]

I used to get scare by trees before watching this playlist. But you are a real gem striver. You have made these hard topics just as a piece of cake. Take a bow🙌

[@sushmi6400]

hey I have a doubt the maximum path is 42 right but if we return like that at last we are getting 25.how is that code correct

[@ShubhamKumar-uf3gc]

the farther I have came in the dsa sheet I have realized lesser is the views on the video which proves the number of people who have dropped themselves from completing the series and that gives me a motive to not be among them and bhai you are magical.

[@AnishS-cp]

Very well explained, covering all cases. Really a golden series even in 2024 ❤❤

[@HarshKumar-os9bx]

a genuine thanks bhaiya for this tree series a month ago not understanding how to think of solution or even take a approach now attempting and solving leetcode hard on own a deep thanks from bottom of the heart really bhaiya I wish ki you may get everything in life

[@saranguru6100]

Hi Striver, I have a doubt, what if all the values in tree are negative? because we return 0 for all if negative subtrees. Anyhow, the explaination is mind blowing!!

[@trueevil2590]

In answer we will return value of maxi so in case of negative left sum or right sum it will set left sum or right sum to zero but maxi will store value of node too and we will return that as our final answrr

[@rishankmehrotra5732]

@@trueevil2590 Thanks. Even I had the same doubt.

[@avicr4727]

we can also pass a variable which store individual node values and compares it

[@ArshadIqbal_IEC_]

leetcode has changed the question a bit so u basically have to intialised a global variable to Integer.MIN_VALUE then you get the answer

[@SagarSureshSrikant]

Wonderful Explanation. Understood the concept very well. Thanks a lot.

[@dank7044]

did this on my own,courtesy of aditya verma(recursion god) and you.

[@stith_pragya]

Thank You So Much for this wonderful video.....................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@abhinavnair4577]

This was the video where the solution clicked!! ..Thanks

[@harshkoshti4588]

You're an awesome striver! 🌟 No KZbinr explains like you. Thank you for such amazing content! 🎉👏

[@krishvaghela3182]

TO Handel Negative Test Cases int maxpath(TreeNode* root,int &ans) { if(root==NULL) return 0; int leftsum=maxpath(root->left,ans); int rightsum=maxpath(root->right,ans); if(leftsumval+max(leftsum,rightsum); } int maxPathSum(TreeNode* root) { int ans=root->val; maxpath(root,ans); return ans; }

[@lifehustlers164]

Completed 18/54 (33% done)!!!

[@sarangtamrakar8723]

Just watching the approach , I am able to solve the complete solution,,,Thanks striver for making Tree so easy... Specially Recursion Series.. helped a lot to understand tree.

[@kingmaker9082]

Similar to that of diameter of binary tree...loved your solution ❤️

[@TarunKumar-cn6in]

I was looking for this video for a long time finally i reached !Thanks 🙏

[@devesh819]

Your Dry Run style always amazed me . Thanks for this Bro.

[@sayantaniguha8519]

but this'll always find the maximum path sum b/w any 2 leaf nodes right? Is that what the Q asks?

[@saketmehta6697]

Omg.. What i just discovered will blow your mind... After thinking for 5 min I am able to understand that this code can also handle all negative nodes test case, let me tell you how.. In case of all negative nodes... left and right will return 0 but... to find the ans we are doing.. max=Math.max(max , left+right+node.val) It means, we are going to pick that node which have the maximum value and that will be the answer... Hope this will help to everyone who have doubt in all negative nodes

[@vadithyavenkat2486]

No bro it gives 0 only because max(0, 0 + 0 -anyVal) gives 0 only

[@keerthireddy8074]

Yes.. I feel the same too

[@keerthireddy8074]

@@vadithyavenkat2486 Yeah.. but the recursive call is still made where it assigns the value to max variable

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@chad._life]

class Solution { public: int height (TreeNode*root,int &sum){ if(root==NULL) return 0; int lsum = max(0, height(root->left,sum)); int rsum =max(0, height(root->right,sum)); sum = max(sum,lsum+rsum+root->val); return root->val+max(lsum,rsum); } int maxPathSum(TreeNode* root) { int sum =INT_MIN; height(root,sum); return sum; } };

[@bhushankorg5606]

In most tree questions if you can solve problem for a single substree You can do it for whole tree.

[@RajatGupta-lq3cb]

Sir, with all due respect, I think we have to consider the case where the left subtree and right subtree both are returning negative values. I think in that case our present node should return it's own value instead of adding it with max(lst,rst). If I'm wrong, please let me know.

[@dawarvaibhav]

The left and right sum become 0 if they are negative. And thus while returning, only node’s value will be returned.

[@RajatGupta-lq3cb]

@@dawarvaibhav but how would the sum become 0? lst and rst could return different integer values na?

[@sans.creates]

@@RajatGupta-lq3cb we are choosing max between 0, sum from left/right so if you get a negative sum, obviously 0 would be picked and things go on. hope that helps!!

[@RajatGupta-lq3cb]

@@sans.creates yeah, it does. Thank you

[@saurabhjha2710]

@@sans.creates what if all the nodes have negative value?

[@shwetagupta8721]

Bhaisahab whatta a explanation man!!! It doesn't seem a hard question .Literally amazed by your teaching skills.

[@RahulKumar-nd2sp]

Are u placed right now?

[@Shantisingh-tz5sr]

You beauty....your logical thinking...this man is not of this universe....

[@lone_wolf7721]

This hard question seems very simpler after your explaination

[@e889.]

If this problem seemed hard to you Goodluck with actual hard leetcode problems 🤣

[@lone_wolf7721]

@@e889. everything has time ..... I am beginner .... At a time getting sum of digits is a hard for me .... Now it is hard ..... I will definitely do better with time ....

[@e889.]

@@lone_wolf7721 👍

[@yashstudio7396]

@@e889. if it was really easy then you were not here... Allthough it's not very hard problem but calling it easier can suppress someone's confidence...

[@rishabhkumar8115]

literally, it doesn't feel like it's a hard question. such a great explantation it is. literally, it doesn't feel like it's a hard question. such a great explantation it is.

[@Zomb-zj4ip]

understood and solved my 2nd hard question. thanks.

[@santanu29]

Taking array for passing as reference is smart. I was thinking how you would pull that off in Java.

[@shubhanganitayal8185]

Please make a video on the removal of maximum number of edges from a tree such that the disconnected subtrees have an even number of nodes.

[@Hemanthkumar-ck1zu]

Initialised the max with ZERO, but we have to initialise it it with INT_MIN to cover the all negative integers testcase :)

[@dhainik.suthar]

What if negative value is -1 and left pointer of this negative value is some max value. What if we want to store path instead of max sum ?

[@robinsingh6119]

return this in the end - "return max(self.sumpath, root.val)"

[@kya_karoge_jaanke1607]

Bhaiya It must include two leaf nodes . Not randomly any two nodes in tree 🌲

[@prabhakaran5542]

Understood ❤

[@evergreen7781]

I solved this, but stuck in that edge case taking those -ves & maxi = INT_MIN 🙈

[@AKASHKUMAR-ui1bd]

THANK YOU SO MUCH SIR APPKE JAISA KOI NAHI PADHATA

[@6mahine_mein_google]

it will not get accepted in the latest update of the leetcode problem as they have mentioned in the end that path will be non-empty , striver's solution worked because empty paths were accepted in the question before. You have to add just a simple check in the end if(leftval + max(left , right); because if both left and right are negative then we should only return node's value and if anyone is positive we can add the maximum of that to our node

[@sarbojitrana007]

i am seeing a lot of confusion in the comment for the case where every number is negative, yes the code provided by sir will not work there instead you can make a small change to it, while updating maxi compare with the current root->val . int sum(TreeNode* root){ if(root == nullptr) return 0; int ls = sum(root->left); int rs = sum(root->right); maxi = max(maxi, max(ls + rs + root->val , root->val)) ; maxi = max(maxi, root->val); int value = root->val + max(ls, rs); if(value < 0) return 0; return value; } this will get accepted

[@shreyxnsh.14]

no it will work if you initialised maxi with INT_MIN

[@abhisheksa6635]

I tweaked the logic to support the negative o/p of left path, right path and root val: class Solution { private: int findMPS (TreeNode* node, int& MS) { if (node == NULL) { return 0; } int l = findMPS(node->left, MS); int r = findMPS(node->right, MS); //For a top Node this logic makes sense MS = max({MS,max(l,r)+node->val, l+r+node->val, node->val}); //For a subnode we have the logic return (max(l,r) + node->val); } public: int maxPathSum(TreeNode* root) { int maxSum = INT_MIN; findMPS(root, maxSum); return maxSum; } }; But for god sake who can build a tree from this: [9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6] If I am not wrong, how come a NULL node has a 2 and NULL as a child, beats me

[@_-6912]

Awesome series Raj, one stop for tree learnings. Raj, could you please let me know if there are more videos coming for Binary Search Trees?

[@amanasrani6405]

Amazing Bhaiyaa

[@RajeevCanDev]

c++ code:- int solve(TreeNode* root,int &maxi){ if(root==NULL)return 0; int leftSum=max(0,solve(root->left,maxi)); int rightSum=max(0,solve(root->right,maxi)); maxi=max(maxi,root->val+leftSum+rightSum); return root->val+max(leftSum,rightSum); } int maxPathSum(TreeNode* root) { int maxi=INT_MIN; solve(root,maxi); return maxi; }

[@sushmi6400]

We want the maximum no so we have to return the maxi no..?

[@aakarzinzuwadia203]

I think the check for value to be negative is at the wrong spot. You do not check after the return of the function. Imagine the max of (left,right) is -30 and node value is 35 then you will get the positive value which is 5. This is wrong. You should add check for negative before the return. If we really have to start and go to end of leaf then this is correct. so I may be wrong.

[@shashankarora2945]

amazing explanation

[@nitingoyal5515]

You are really God in disguise, I completed your Graph Series and now I am here doing trees. Your content is really great and I really appreciate your efforts

[@bhavkushwaha]

Thankyou Striver, Understood!

[@m.afnan2018]

Badhiya explaination tha bhaiya,,, Soo Simple,,,, Maza aagya,,,,

[@rahulpai5559]

Was struggling and breaking my head with my own soon then saw conventional soln video it is horrible STRIVER is damn within 10 mins with a simple intuition solved it

[@rahulpai5559]

*soln

[@akhilesh33056]

Can't we write in base condition if(node== Null || node -> data < 0) return 0; 🤔

[@SanketKolte-q9d]

what about test cases like - [-1, -5] [-5] this will not work fine!

[@kmchary1181]

Great explanation man. You are awesome.

[@rakshayadav1892]

Python code: class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: self.mx=-10000000000000 self.helper(root) return self.mx def helper(self,root): if not root: return 0 l=max(self.helper(root.left),0) r=max(self.helper(root.right),0) self.mx=max(self.mx,l+r+root.val) return root.val+max(l,r)

[@vedbhatt6777]

May I know the reason behind self.mx=-1000.. and not self.mx=0. I took the latter one and it didn't work

[@tps8470]

Loved the explanation

[@muditshrivastava695]

****** As the maxi is already defined in the function from where we are returning maxi value, so by default it will take the the defined value i.e., INT_MIN or 0, which is not the answer. To get the right answer we want the argument to modify according to the called function so we have to pass the argument by reference. It will modify the value of argument in that particular address and we will get the right answer while returning from the maxPathSum function.

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@unknown47896]

WE CAN DO LIKE THIS ALSO int maxi=0; int f(TreeNode* root,int &maxi) { if(root==NULL) return 0; int leftsum= f(root->left,maxi); int rightsum=f(root->right,maxi); if(leftsumval+ max(leftsum,rightsum); } int maxPathSum(TreeNode* root) { if(root==NULL) return 0; maxi=root->val; f(root,maxi); return maxi; }

[@immrhrr]

this code handles all the possible cases when nodes are negative positive or zero int f(BinaryTreeNode*root,int &maxi){ if(root==NULL)return 0; int leftsum=f(root->left,maxi); int rightsum=f(root->right,maxi); int currentMax = max(root->data, max(root->data + leftsum, root->data + rightsum)); // Calculate the maximum path ending at the current node maxi = max(maxi, max(currentMax, root->data + leftsum + rightsum)); // Update the maximum path sum found so far return (root->data)+max(leftsum,rightsum); } int maxPathSum(BinaryTreeNode *root) { int ans=INT_MIN; f(root,ans); return ans; }

[@batuklal]

dude ur code is so wrong no way its passing any negative test case why are u even posting this??/

[@sauravchandra10]

Satisfaction is when you are able to code the problem without even looking starting the video :)

[@btsarmy6249]

Why we are considering left as max of 0 and maxPathSum(node.left). In which case will it give wrong answer if we don't consider this?? Is there any significant difference in output using this instead of simply using left = maxPathSum(node.left) ??

[@jambajuice07]

how will it pass the edge case where all node values are negative ?

[@cinime]

Understood! Super awesome explanation as always, thank you very much!!

[@mahendrasinghpuniya548]

this solution code fail for the testcase [-2,-1]

[@knowledge-n9z1w]

we want to return max( maxi , max(left,right) + node->val ) then we get maxi value if it is greater??

[@anupreetsihra2732]

what if we have 200 in node value on left of -30 ?? in seco d examzple it can give us max sum but we make it 0 so how will it work ?, it can still if if we make -ve zero

[@AnkitVishwakarma-n8c]

Striver you are really amazing.The way you make these topics easier is great. I am currently on BinaryTree videos..

[@SriDuttRugada]

what if they ask to find max path from node A to node B (which is a leaf node)?

[@muskangupta5873]

Please update the description L28 is the pre-requisite video for maximum width calculation

[@SriDuttRugada]

should we have to solve every tree question using recursion and back tracking or is there any method

[@Parth.Deshpande]

Beautiful explanation !!! 🔥

[@vishukumar9211]

osm solution , i saw many solution , i was not getting the logic but you hats off to you .

[@kadurkaz4691]

Gods grace i have solved on my own ....or else i would have stopped trees here

[@bhagyashri7729]

Negative sum scenario should have been covered on the go.

[@mriduljain1981]

completed Lecture 17 of Tree playlist.

[@tomjerry0796]

Great great explanation ❤🎉 We can achieve O(1) space complexity by declaring a private int max variable as a global variable, pin this comment to know everyone

[@iamnottech8918]

Easy one!! thanku

[@bhawna1997]

Striver, I have a doubt. If we consider a case like this tree= [-2,7,30,null,-20,-50,10], if we add up the node value with left and right sum the maximum would be (-50+30+10) that is -10 but we can have a maximum path sum considering a=30,b=10 as 40. So shouldn't we compare first to update maximum with either max of all three, or node and left, node and right? Please correct me if I got something wrong

[@bhawna1997]

@Kartik Kalia Got it, Thanks !

[@debangshubanerjee1311]

@Kartik Kalia bro can u explain this a little more dint get what exactly u r trying to mean...

[@gamingwithasmile268]

@@debangshubanerjee1311 just change the last line. .. return max(node.val, (node.val+max(leftsum,rightsum)))

[@sumitsinha995]

bhaiya last return statement wala badiya bataya waha confusion tha!

[@raven_claw887]

Had hard time figure out what's in return, understood from your dryrun

[@akaxh_ut]

Great explanation bhaiya, your lectures are just amazing.