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 TH-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 :)

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

[@sangramkapre]

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

[@techdose4u]

:)

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

[@MyLifeMyWorld08]

One of the best explanation Surya. Thanks

[@techdose4u]

Welcome

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

[@mikasaackerman2694]

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

[@techdose4u]

Thanks

[@raviagarwal4287]

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

[@techdose4u]

Thanks :)

[@m.praneethreddy7335]

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

[@aneeshsharma]

Very good explanation of the Cases. Thank You !

[@techdose4u]

Welcome bro :)

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

[@utkarshgupta6258]

By far the best explanation

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

[@sayyadalikhan3702]

Excellent explanation! Best Video for Binary tree maximum path sum

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

[@harshagarwal2629]

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

[@techdose4u]

Thanks

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

😅

[@Neerajkumar-xl9kx]

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

[@techdose4u]

Welcome :)

[@saumya1singh]

Very Well Explained!

[@techdose4u]

Thanks

[@sarahzaman3173]

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

[@techdose4u]

Welcome 😊

[@biswaMastAadmi]

excellent explanation ! keep going !

[@techdose4u]

Thanks ☺️

[@viralmehta2542]

very nicely explained in detailed.

[@julietgeorge4858]

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

[@harishkumarreddy079]

very good explanation for a hard problem

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

[@PriyankaSharma02499]

Very nice explanation

[@techdose4u]

Thanks

[@aryamarda1643]

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

[@hiteshgupta7652]

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

[@techdose4u]

They will come in may challenge :)

[@dimplerohara3799]

Best explanation so far!

[@techdose4u]

Thanks :)

[@anujasrivastava3446]

This is a really nice explanation! Thank you!

[@techdose4u]

Welcome :)

[@InderjeetSingh-no3pp]

Nice explanation.....easily understandable

[@techdose4u]

Thanks :)

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

👍

[@varunnadipudi2257]

Well done!!Explanation is very nice.

[@techdose4u]

Thanks

[@adityadhikle9473]

Amazing explanation!!! Thank you

[@competitivedoritos4294]

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

[@techdose4u]

Welcome :)

[@deviprajwala9779]

Amazing explanation!!

[@techdose4u]

Thanks

[@AnkitKumar-mb4vl]

Great explanation ❤️

[@techdose4u]

Thanks :)

[@vaibhavjain4710]

Best explanation , I have ever seen ;)

[@techdose4u]

Thanks :)

[@aashishkalia8269]

You explain really nice and simple !!

[@techdose4u]

Thanks :)

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

[@dhruv2014]

Great explanation

[@mansibhardwaj3976]

Excellently explained!!

[@techdose4u]

Thanks

[@markos8955]

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

[@techdose4u]

Thanks :)

[@kamalkantrajput7684]

thank u so much Bhaiya

[@techdose4u]

Welcome :)

[@chhaviagarwal7514]

very well explained.. Thanks

[@techdose4u]

Welcome

[@aniketsriwastva6345]

Great Explaination Sir

[@techdose4u]

Thanks

[@recklessekta]

very well explained, thanks!

[@techdose4u]

Welcome :)

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

[@ayushthakur733]

Amazing explanation 👌

[@techdose4u]

Thanks 😀

[@usrivastava92]

brilliant explanation.. thanks alot.. :)

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

[@harshagarwal2629]

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

[@techdose4u]

Will try

[@ketanahuja8939]

Wonderful

[@techdose4u]

:)

[@tanmayagupta4591]

Thanks!

[@techdose4u]

Welcome :)

[@LaxmiNarayana-zs5vz]

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

[@PhoenixRisingFromAshes471]

outstanding solution brother

[@techdose4u]

Thanks bro :)

[@chetanpatteparapu7600]

Thank you very much Mate. Very nice explanation

[@techdose4u]

Welcome :)

[@yuhaokong]

ok this explanation is pretty damn clear

[@techdose4u]

Thanks :)

[@humansofcrypto9746]

Excellent!

[@techdose4u]

Thanks :)

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

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

[@samkitjain2136]

bhai aap legend ho yaar

[@RahulKumar-wv4ti]

Thanks bro

[@techdose4u]

Welcome

[@willturner3440]

Thanks bhai

[@techdose4u]

Welcome

[@mohamedmusaraf675]

Thanks a lot.!!

[@factsclub4u]

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

[@programmingstuff5741]

These are also such questions to prepare for. Interviews

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

[@divyamgupta2100]

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

[@chaunguyen8202]

Thank you!

[@techdose4u]

Welcome

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

[@sanky52]

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

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

👍

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

[@yashgoswami5374]

good explanation sir

[@saiteja8870]

🔥🔥🔥🔥

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

👍

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

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

[@pawanchandra9193]

Dope

[@x12624]

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

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

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

[@subham-raj]

*This is so sexy*

[@techdose4u]

Welcome bro :)

[@salonikaur7043]

Why do we return case 1 in the helper function?

[@huansir1922]

buddy , your view is special

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

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

[@indsonusharma]

Great man I did this same too bus mera live video me reply de diya karo haha

[@techdose4u]

Live video mein itne comments aate hain ke sambhal hi nhi paata 😅 random answer deta hun....don't mind.

[@bhairavas2528]

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

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

[@midhileshmomidi3120]

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