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

[@jeet-smokey]

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

[@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.

[@souradeepkar]

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

[@aavashkuikel1341]

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

[@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

[@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

[@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

[@shreyansharora1320]

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

[@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; };

[@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!

[@ananttyagi7372]

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

[@ritikshandilya7075]

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

[@audioeditsnstuff]

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

[@lifehustlers164]

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

[@dank7044]

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

[@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

[@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

[@AnishS-cp]

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

[@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.

[@JayaSingh1063]

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

[@abhinavnair4577]

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

[@stith_pragya]

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

[@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...

[@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

[@harshkoshti4588]

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

[@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

[@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; }

[@SagarSureshSrikant]

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

[@devesh819]

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

[@Shantisingh-tz5sr]

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

[@nawabkhan4916]

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

[@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.

[@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

[@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 🙏

[@sayantaniguha8519]

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

[@bhushankorg5606]

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

[@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.

[@kya_karoge_jaanke1607]

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

[@prabhakaran5542]

Understood ❤

[@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 :)

[@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?

[@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

[@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; }

[@Zomb-zj4ip]

understood and solved my 2nd hard question. thanks.

[@shashankarora2945]

amazing explanation

[@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 ?

[@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; } };

[@tps8470]

Loved the explanation

[@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

[@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?

[@santanu29]

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

[@amanasrani6405]

Amazing Bhaiyaa

[@sauravchandra10]

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

[@kmchary1181]

Great explanation man. You are awesome.

[@robinsingh6119]

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

[@bhavkushwaha]

Thankyou Striver, Understood!

[@m.afnan2018]

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

[@knowledge-n9z1w]

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

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@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

[@muskangupta5873]

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

[@vishukumar9211]

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

[@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??/

[@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

[@bhagyashri7729]

Negative sum scenario should have been covered on the go.

[@jambajuice07]

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

[@UCHSimrankumari]

nice explanation

[@cinime]

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

[@parul8334]

understood, love u sir ❤❤

[@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; }

[@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) ??

[@Parth.Deshpande]

Beautiful 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.

[@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

[@sumitsinha995]

bhaiya last return statement wala badiya bataya waha confusion tha!

[@rawat_ji5183]

perfect explanation thank you for such a great explantation

[@anamikaahmed4887]

Pre-requisite videos" Max Width of BT: kzbin.info/www/bejne/kJPck4ysmLt_odU Max Height of BT: kzbin.info/www/bejne/m3WWpaCFa5uUeKM

[@mriduljain1981]

completed Lecture 17 of Tree playlist.

[@AnkitVishwakarma-n8c]

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

[@amreenmazhar]

Will it work for [-1,2] as a binary Tree

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@apmotivationakashparmar722]

Thank you so much.

[@raven_claw887]

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

[@sushmi6400]

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

[@akhilesh33056]

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

[@akaxh_ut]

Great explanation bhaiya, your lectures are just amazing.

[@iamnottech8918]

Easy one!! thanku

[@abhinav8804]

How to handle the case where all nodes are negative? Since, through the code explained by you answer will be zero, while, it will be the least negative number in that case.

[@Arshi728]

We are getting max = max(max, left, right, node.val), in case of all -ve nos. , left and right surely be -ve, and we make it 0, it will still get the value of node in max. So for every node, we are considering the node's value. So That means if all nodes are negative, we are taking all into consideration to calculate the max. If you have done Kadane's Algo, just think of this case with that algorithm.

[@tanveer.shaikh]

i was solving correctly but missed basic like adding node val while taking max

[@shaikfahim1232]

Brute force bhi daal dete to accha hota bhayya

[@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)))