2 things of note for myself: 1) the recursive method returns only one child leg upwards because that's all that's useful to the parent. 2) the actual max contender calculation happens in only one place and it's in the form of "add me and what my left and right legs give me together". i would have thought there would be a 2nd version of this calculation in the solution (for a different shaped path), but it's folded away by clever math/logic previously. and 3) also all possible solution paths are of only one general shape = [[ left toe -> up to crotch -> down to right toe ] ] - one or both legs might be chopped off, but it's still based off that. and 4) "zero?? why zero?" - it's a shortcut - for the math it feeds to upstream it equates to "pretend this is a null child or null leg, i.e. pretend this part of the tree doesn't exist". whether the number is 0, or -2, or -200000 makes no difference....its a leg that we can abandon from all further calculations.
Thanks so much for the animation and code walkthrough! I finally understood the recursion concept in this problem and also why I need to add 0 to this piece of code to eliminate node value less than 0. int left = Math.max(postorder(root.left), 0); I second to what others said, excellent animation and explanation. Thanks!
The way u hv explained this solution hats off.. I had gone through many other explanations on RUclips but none gave me confidence that i can solve it even looking the answer.. this is the perfect representation just perfect. Commenting here just to encourage ur efforts what u r doing. Commented liked subscribed 👍🏻☺️
This really is the best explanation out there for this problem. I was beating my head against the wall the entire time I was trying to solve it but this video really cleared everything up for me. Thanks for sharing!
Please correct me if I am wrong: 1. when you consider a subtree as the path, that is to split at current node, you sum over children's value and parent's value and update the global max 2. Otherwise, get the maximum value between left and right child, add it to the parent's value and return it to the previous level. Thanks.
If our left node and right node are both negative, how do we account for which one will reduce the current node's value the least? Are we able to stop our path at that node since anything further than that would result in a negative sum?
Thanks for putting together a great explanation; though it's not immediately clear to me why do we do left + root.val + right when calculating max. We know that the path can't be of Y shaped but we're still adding values that form a Y shape.
Thanks for this nice explanation. I think there is conflict between how you are explaining the algorithm about handling the negative nodes versus how you coded. we do return negatives from our children however we ignore them afterwards.
at 5 : 40 you say we can't choose both, but this specific case we actually CAN choose both coz we are NOT re-visiting any node , BUT lets just say we can't still visit coz its a negative number and NOT useful when it comes down to MAX SUM PATH.... let me know if you think i'm incorrect EDIT 1: The proof of what I said can be found at 7:30 😃
Seems like you are simply mutating the global variable of max. Since you're not doing anything with the return value of postorder function, you can simply make it a void function. Great video to give the audience visuals btw. Gave you a thumbs up and a subscribe.
Good explanation. One suggestion: always initialize max to Integer.MIN_VALUE in the int maxPathSum(Node root) method so that successive calls can be made.
Just be careful to declare the variable outside of the method! If it is declared AND initialized in maxPathSum then it will not be available in the scope of the postorder method.
This may be the least on point question to this video. How, at 10:13 (ish), did you get your dual line cursor to be aligned at a different position on lines 27 and 28?
No because we always add the node value even if it is a negative number and check if that is the new max. So if all of the tree was negative, the smallest negative number by itself would be the max.
Without any doubt, the best explanation on this problem !!! But why poatorder travesal? I think this is the key. Could you please tell a little about the thinking process linking to the key? It would be a pefect video with 10/10. Thanks!
Postorder always will visit the three nodes bottom up and for this problem we need to be computing max's in a bottom up approach. Hope that makes sense!
man i feel bad u dont have more subs. not for u, but if u had more subs I'm sure u wud have worked harder and churned out more such videos. anyways, great service
What if the whole tree consists of negative numbers only, then in your case wouldn't it be returning zero instead of the maximum of all the negative numbers?
how the f are we supposed to figure this out in an interview?? I can see coming up with the brute force approach, but the returning 0 stuff is very specific. Is this a common pattern that we would also see in other problems?
Sorry this comment is late, but the reason why is because the recursive function will continuously move left until it hits the base case of the node being null. After that it moves back up the parent and goes right, then explores the left subtree again.
Big up to this guy. I think he has the best explanations of leetcode problems. the animations really help if youre a visual learner
Dude that is such a huge compliment, thank you
This was sick! Making those animations takes a lot of additional effort - very much appreciated dude!
Thank you! The animations I feel is the best way to learn these problems, so it is worth it!
@@AlgosWithMichaelabsolutely 🎉
From one Michael to another, way to make our tribe proud with such good work.
2 things of note for myself:
1) the recursive method returns only one child leg upwards because that's all that's useful to the parent.
2) the actual max contender calculation happens in only one place and it's in the form of "add me and what my left and right legs give me together". i would have thought there would be a 2nd version of this calculation in the solution (for a different shaped path), but it's folded away by clever math/logic previously.
and
3) also all possible solution paths are of only one general shape = [[ left toe -> up to crotch -> down to right toe ] ] - one or both legs might be chopped off, but it's still based off that.
and
4) "zero?? why zero?" - it's a shortcut - for the math it feeds to upstream it equates to "pretend this is a null child or null leg, i.e. pretend this part of the tree doesn't exist". whether the number is 0, or -2, or -200000 makes no difference....its a leg that we can abandon from all further calculations.
Thanks so much for the animation and code walkthrough! I finally understood the recursion concept in this problem and also why I need to add 0 to this piece of code to eliminate node value less than 0. int left = Math.max(postorder(root.left), 0); I second to what others said, excellent animation and explanation. Thanks!
This video is the clearest explanation on the internet!!!! Thank you so much Michael!!!
Your videos are quite high class and you explain a very complex problem in the possible easiest way. You deserve more followers/subscribers.
Thank you very much!
The way u hv explained this solution hats off.. I had gone through many other explanations on RUclips but none gave me confidence that i can solve it even looking the answer.. this is the perfect representation just perfect. Commenting here just to encourage ur efforts what u r doing. Commented liked subscribed 👍🏻☺️
I can't thank you enough for this video. Really appreciate it Michael!
This really is the best explanation out there for this problem. I was beating my head against the wall the entire time I was trying to solve it but this video really cleared everything up for me. Thanks for sharing!
Of course!
This is the best explanation of this problem! This one makes the other explanations look like copy pasting works without any level of understanding
Thank so much!
Best explanation on youtube with good animation thank you man!
Wow, thanks!
Please correct me if I am wrong:
1. when you consider a subtree as the path, that is to split at current node, you sum over children's value and parent's value and update the global max
2. Otherwise, get the maximum value between left and right child, add it to the parent's value and return it to the previous level.
Thanks.
Thank you for animating this. Best explanation I found on this problem.
No problem, glad it was helpful for you!
This channel is based and redpilled and should have more subscribers. COMMENT TO BOOST THE ALGO!
SO TRUE!
another amazing video! I loved the tree animation walkthrough, it was super helpful and your explanation was concise and clear as usual :)
Thank you! I'm glad it was helpful :)
This is a fantastic explanation, and as others have said, the visual explanation is exquisite.
Thank you! More to come!
Thank you thank you! BTW watching you writing codes is something eye-pleasing bro is so clean and very level-minded
Thank you, I'm glad you got like the video!
Thanks Michael for such a wonderful animation. Looking forward to more such videos on trees
I plan to do a lot more tree problems
Michael has the best explanation videos!
Glad you like them!
This is the best explanation video for this question. Thank you, brother. Keep making more videos like this. I liked and subscribed to you.
Thanks for the sub!
Pls do more blind 75 qns!! Love the way u explain the approach with those animations. Looking forward to future videos :)
best explanation on this - thank you!
Wow I loved the way you explained that! Thank you!
Say hi to roo
If our left node and right node are both negative, how do we account for which one will reduce the current node's value the least? Are we able to stop our path at that node since anything further than that would result in a negative sum?
Nice animation , just by seeing it , i coded own my own and its variation too , thank you
This is the best explanation provided, thanks !!
Thanks!
Thanks for putting together a great explanation; though it's not immediately clear to me why do we do left + root.val + right when calculating max. We know that the path can't be of Y shaped but we're still adding values that form a Y shape.
exactly my point!
I think its because that individual (left + root + right) might also be the max_sum_path we are looking for
I like your videos! Question on 00:37 - Sum for the Path from 10 to -5 should be 10. You mentioned 0. What am i missing?
That explanation was really helpful. Thanks for helping the community. Love from india ❤️
Happy to help!
Your explanation was Godlike! Thank you very much!
Good explanation. Question at 4:34 we substitute 0 in place of -5 but 7:01 we add -10 instead of 0. Why is that?
Crystal clear. You rock it!
Thanks for this nice explanation. I think there is conflict between how you are explaining the algorithm about handling the negative nodes versus how you coded. we do return negatives from our children however we ignore them afterwards.
Great, and tree traversal visualisation is awesome
we return max (left, right) + root.data because we need the straight path.
Thank you! I'm glad it was helpful
at 5 : 40 you say we can't choose both, but this specific case we actually CAN choose both coz we are NOT re-visiting any node , BUT lets just say we can't still visit coz its a negative number and NOT useful when it comes down to MAX SUM PATH.... let me know if you think i'm incorrect
EDIT 1: The proof of what I said can be found at 7:30 😃
You're awesome man. Keep it up!
Appreciate it!
Seems like you are simply mutating the global variable of max. Since you're not doing anything with the return value of postorder function, you can simply make it a void function. Great video to give the audience visuals btw. Gave you a thumbs up and a subscribe.
Good explanation. One suggestion: always initialize max to Integer.MIN_VALUE in the int maxPathSum(Node root) method so that successive calls can be made.
Just be careful to declare the variable outside of the method! If it is declared AND initialized in maxPathSum then it will not be available in the scope of the postorder method.
Michael is the CEO of being epic!
Accurate
You should make a Udemy course for interview prep. I would buy in a second!
I agree. His explanations are like ABC. I can understand graph problems now just because of this channel
This may be the least on point question to this video. How, at 10:13 (ish), did you get your dual line cursor to be aligned at a different position on lines 27 and 28?
Hold control and click :)
Thanks a lot for the animation and code walkthrough!
No worries!
for the code, how it can be memorized ?
thank you so much man, for the explanation and code walk-through.
Glad it helped!
You deserve atleast 1million subscribers !!!
Thank you!!!
Great explanation! i was able to solve it by just looking at your algo explanation!
That's awesome! nice job
Thanks for sharing this. Does replacing negatives with zero cause problems when the entire tree is negative?
No because we always add the node value even if it is a negative number and check if that is the new max. So if all of the tree was negative, the smallest negative number by itself would be the max.
@@AlgosWithMichael i see it now. thank you!
Thank you for the video Michael I could not understand why we choose 0 instead of -5 but when it came to -10 we did not choose 0
finally I understand, thank you so much!
Glad it helped!
Really appreciate your effort bro...specially that animation
Thank you so much 😀
I don't understand. On line 29, you assign a variable "max" but never use it.
Great explanation and visuals!
Without any doubt, the best explanation on this problem !!!
But why poatorder travesal? I think this is the key. Could you please tell a little about the thinking process linking to the key? It would be a pefect video with 10/10. Thanks!
Postorder always will visit the three nodes bottom up and for this problem we need to be computing max's in a bottom up approach. Hope that makes sense!
man i feel bad u dont have more subs. not for u, but if u had more subs I'm sure u wud have worked harder and churned out more such videos. anyways, great service
I appreciate it! I don't do it for the subs, but more subs would be great haha
10:40 why is this Math.max used? i can't understand the reason
Because we are trying to figure out the max path. If we didn't use the max function you would only be calculating local maximums
What if the whole tree consists of negative numbers only, then in your case wouldn't it be returning zero instead of the maximum of all the negative numbers?
That's why we initialise max is -inf and not zero
Nice explanation!! Keep rocking Bro!!!
Thank you!
how the f are we supposed to figure this out in an interview?? I can see coming up with the brute force approach, but the returning 0 stuff is very specific. Is this a common pattern that we would also see in other problems?
If you do enough recursive BT problems, you will get experience solving them with subtle nuances. This question definitely is harder than most though
It was really helpful brother
Thanks !
Anytime
Great animations! :)
Thanks! 😄
Thank you so much !!
love the explaination , thanks
Thank you
Best video for this problem
Thank you!
Thanks, this helped a ton!
Glad it helped!
Thanks bro. I love you.
Thank you so much dude.
No problem!
thanks for awesome video
I just don't understand how it started from the bottom of the tree based on the code? Can anybody explain it to me?
Sorry this comment is late, but the reason why is because the recursive function will continuously move left until it hits the base case of the node being null. After that it moves back up the parent and goes right, then explores the left subtree again.
Mind blowing animation video bro
Thank you so much 😀
thanks... really helpful
Great explanation!
Thanks!
great explanation. Thank you
You are welcome!
Nicely done!
Thanks!
Good explanation as always
I appreciate that!
I got this question in my Amazon onsite and I got totally flustered. I have my Google phone screen next week and I am very scared
Best of luck to you!
Thanks for the video. Still not clear why it should be rounded to 0.
I meant at 5:12
We round to zero because if we return a negative number, the max sum can only get smaller.
This is gold
Thanks!
Amazed.
Haha thank you
perfectt
Thanks!