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.
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.
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!
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
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; } }
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; } }
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]
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}; } }
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.
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 :)
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; }
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 :)
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 }
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.
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?
@@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.
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.
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......
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?.
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.
1:09 - EXAMPLE 2 IS INCORRECT. max sum = 6 (not 5) and includes the root, and the rightest node
Sir , this explanation deserves much more applaud , that's why I shared your channel to all my juniors.
Seen a few explanations on UA-cam, this is the best one so far, way to go!
:)
@@techdose4u yea the best one
The example which you have illustrated where the sum was 5, the maximum sum we can achieve is 3->2->(-1) ->2 sum=6
Probably the best explanation of this problem on You Tube .. Thanks Man
Welcome :)
Really good explanation. I started to understand the logic when with a playback speed of .75. Thanks
Nice :)
Best channel in the youtube for data structures and algorithms👌👌
Well explained with example 🍁 , Smart way by using the three cases it clear all my doubts 👍🏻.
Thanks man :)
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.
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.
Thanks :)
This is the best explanation I have come across for this question.
Thanks :)
Nice! The only explanation I understood on UA-cam :-)
:)
By far the best explanation
One of the best explanation Surya. Thanks
Welcome
worlds best video ,sir aur bnayo aisi interview bit se lekr ,clear all the doubts
Thanks
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!
Thanks. Because there might be a max sum path in either left or right subtree which is not rooted at current node.
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
Respect for the effort! 🙃.
Thank you for the great content and please , if you are comfortable,teach us about graphs after the leetcode saga😅
Supppppppperrrrbbbbb explanation....U just made a hard problem look so easier . Explanation is awesome :)
Thanks
The way in which you explained this complex problem is lit💥
Keep it up👍
Thanks :)
thank you, this was the best explanation I could find.
Welcome 😊
Very good explanation of the Cases. Thank You !
Welcome bro :)
Excellent explanation! Best Video for Binary tree maximum path sum
Thanks :)
No one Can Explain Like You .
😁 Thanks
can't be explained better than this...thank you
Welcome :)
I was able to do it by your bt diameter ques. Explanation.
Thank you 😀
very nicely explained in detailed.
Best explanation so far!
Thanks :)
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;
}
}
Thank you for showing/explaining the algorithm before the code. I use javascript and so it is helpful.
Nice explanation!! The solution felt really intuitive after looking at this video
Thanks
very good explanation for a hard problem
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.
Welcome :)
This is a really nice explanation! Thank you!
Welcome :)
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
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;
}
}
Thanks for sharing
Well done!!Explanation is very nice.
Thanks
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]
This is a hard problem to understand but sir you made it easy❤️
👍🏼
@@techdose4u sir can we have a video on🙏 print all ''k"" sum paths in a Binary tree🙏
for input -9 6 -10 output is 6 but expected output is -13 in gfg
i searched tons of resource but couldn't understand this problem, thank you so much sir for this video :)
Welcome :)
@Techdose just one doubt i had why we are returning case 1 value only and hence returning max_straight .Please give clear explaination.
Nice explanation.....easily understandable
Thanks :)
Best explanation , I have ever seen ;)
Thanks :)
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};
}
}
👍
Amazing explanation!. Do you mind sharing where do you work?
Currently I am teaching students and working professionals and guiding them to get better opportunities :) Follow me on LinkedIn to know more
Very Well Explained!
Thanks
You explain really nice and simple !!
Thanks :)
excellent explanation ! keep going !
Thanks ☺️
Very nice explanation
Thanks
Thanks for the great explanation!.
how to actually store the path and print the nodes involved in our maximum path?
very well explained.. Thanks
Welcome
Nice Explanation........Nice to see having no Dislikes.
Thanks :)
very well explained, thanks!
Welcome :)
Please make video on path sum question where we have to check if path with given sum exists on leet code
Maybe I will take this when I do TREE.
Excellently explained!!
Thanks
Can you explain why only case 1 is returned, only that part is confusing me.
Great explanation ❤️
Thanks :)
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
Yes you are correct. Actually I wanted it to be -2 but it turned out to be 2. My bad. Consider that -2.
@@techdose4u okay sir thanks
Thanks for pointing out :)
@@techdose4u one doubt sir...I also solve problems in C++ ...and I wanted to ask what those code statements at line 29,30 mean ?...
Amazing Explanation Sir, Looking forward to more hard questions like these!
They will come in may challenge :)
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.
Thank you very much Mate. Very nice explanation
Welcome :)
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 :)
thank u so much Bhaiya
Welcome :)
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;
}
👍
Great Explaination Sir
Thanks
Amazing explanation!!
Thanks
These are also such questions to prepare for. Interviews
Hey, please make a video on sum of distances in a tree question from leetcode .
Will try
So beautiful, I done it the hard way it got AC anyway, I was unsure of what to return to the parent LOL
😅
outstanding solution brother
Thanks bro :)
Wonderful
:)
Amazing explanation 👌
Thanks 😀
bhai aap legend ho yaar
Great explanation
Thanks :)
Can you please mention TC and SC for this approach??
Amazing explanation! Thanks a lot
Welcome :)
Thanks!
Welcome :)
Excellent!
Thanks :)
Why do we return case 1 in the helper function?
Thank you!
Welcome
Thanks a lot.!!
Thanks bro
Welcome
Why is it traversing to every node 3 times? It looks like the traversal just visits each node once.
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 :)
Why are we returning the case1 value at the end instead of the result?
ok this explanation is pretty damn clear
Thanks :)
good explanation sir
brilliant explanation.. thanks alot.. :)
Welcome :)
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
}
Looks messy 😅
@@techdose4u yeah youtube doesn't support code yet ig
**** 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;
}
👍
Thanks bhai
Welcome
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.
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?
@@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.
@@techdose4u gist.github.com/evgeni-nabokov/d67d098aea95e48e20bb0c219983257d
How to come up with this solution in interview if we have not seen this problem before?
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.
@@techdose4u I learnt this the hard way. Thanks for the awesome video
Why we are return max_ straight instead of result.🤔🤔🤔
how much time and practice needs to solve problems like this?
n how to do?
sir, why we return ms after three case??
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......
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?.
0.43 example 2 : Max sum is 6 not 5.
Why you returning max_straight in recursion function.
I got it bcz we want left and right value of curr node that's why returning max_straight
why we returning max_s instead result???
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.
got the solution keep uploading more videos it help our coding skills