Binary Tree Maximum Path Sum (Animated Walkthrough) (LeetCode)

[@stephandowless1297]

Big up to this guy. I think he has the best explanations of leetcode problems. the animations really help if youre a visual learner

[@AlgosWithMichael]

Dude that is such a huge compliment, thank you

[@darksalmon]

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.

[@mpedzi031]

From one Michael to another, way to make our tribe proud with such good work.

[@kamildabek_]

This was sick! Making those animations takes a lot of additional effort - very much appreciated dude!

[@AlgosWithMichael]

Thank you! The animations I feel is the best way to learn these problems, so it is worth it!

[@jrajesh11]

@@AlgosWithMichaelabsolutely 🎉

[@DED_Search]

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.

[@suwin1051]

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!

[@zhiqianzhang5772]

This video is the clearest explanation on the internet!!!! Thank you so much Michael!!!

[@tanvirahmadarjel6047]

Your videos are quite high class and you explain a very complex problem in the possible easiest way. You deserve more followers/subscribers.

[@AlgosWithMichael]

Thank you very much!

[@nipnip9400]

This channel is based and redpilled and should have more subscribers. COMMENT TO BOOST THE ALGO!

[@terrencecrawford3308]

SO TRUE!

[@chaericherry1]

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!

[@AlgosWithMichael]

Of course!

[@rio512hsu]

This is the best explanation of this problem! This one makes the other explanations look like copy pasting works without any level of understanding

[@AlgosWithMichael]

Thank so much!

[@TheMadisonBluesBand]

This is a fantastic explanation, and as others have said, the visual explanation is exquisite.

[@iRockTheBeat1]

I can't thank you enough for this video. Really appreciate it Michael!

[@pryshrng]

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.

[@abhigyanraha5620]

exactly my point!

[@Roxeo1990]

I think its because that individual (left + root + right) might also be the max_sum_path we are looking for

[@pawanverma9605]

The way u hv explained this solution hats off.. I had gone through many other explanations on KZbin 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 👍🏻☺️

[@puneethj9920]

Best explanation on youtube with good animation thank you man!

[@AlgosWithMichael]

Wow, thanks!

[@IChowdhury01]

Thank you for animating this. Best explanation I found on this problem.

[@AlgosWithMichael]

No problem, glad it was helpful for you!

[@KateRipley]

another amazing video! I loved the tree animation walkthrough, it was super helpful and your explanation was concise and clear as usual :)

[@AlgosWithMichael]

Thank you! I'm glad it was helpful :)

[@edgargranados1676]

Michael has the best explanation videos!

[@AlgosWithMichael]

Glad you like them!

[@anssha2643]

Thanks Michael for such a wonderful animation. Looking forward to more such videos on trees

[@AlgosWithMichael]

I plan to do a lot more tree problems

[@ruthylevi9804]

best explanation on this - thank you!

[@terrencecrawford3308]

Michael is the CEO of being epic!

[@nipnip9400]

Accurate

[@therollingambit5222]

Pls do more blind 75 qns!! Love the way u explain the approach with those animations. Looking forward to future videos :)

[@mayurmitkari2215]

This is the best explanation provided, thanks !!

[@AlgosWithMichael]

Thanks!

[@ajaib1313]

Nice animation , just by seeing it , i coded own my own and its variation too , thank you

[@harpercfc_]

Thank you thank you! BTW watching you writing codes is something eye-pleasing bro is so clean and very level-minded

[@AlgosWithMichael]

Thank you, I'm glad you got like the video!

[@xujia1001]

Crystal clear. You rock it!

[@anshumanyadav9871]

This is the best explanation video for this question. Thank you, brother. Keep making more videos like this. I liked and subscribed to you.

[@AlgosWithMichael]

Thanks for the sub!

[@Shellyanne5]

Wow I loved the way you explained that! Thank you!

[@AlgosWithMichael]

Say hi to roo

[@supax2]

You're awesome man. Keep it up!

[@AlgosWithMichael]

Appreciate it!

[@ALEXANDER6888]

Your explanation was Godlike! Thank you very much!

[@nipnip9400]

You should make a Udemy course for interview prep. I would buy in a second!

[@joyceawesome1705]

I agree. His explanations are like ABC. I can understand graph problems now just because of this channel

[@akbar55555shaikh]

Great, and tree traversal visualisation is awesome we return max (left, right) + root.data because we need the straight path.

[@AlgosWithMichael]

Thank you! I'm glad it was helpful

[@ookaluke6769]

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?

[@khadijaashraf]

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.

[@aakashshivanshu3578]

That explanation was really helpful. Thanks for helping the community. Love from india ❤️

[@AlgosWithMichael]

Happy to help!

[@spyderwon2573]

Thanks for sharing this. Does replacing negatives with zero cause problems when the entire tree is negative?

[@AlgosWithMichael]

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.

[@spyderwon2573]

@@AlgosWithMichael i see it now. thank you!

[@GenesisWithin]

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?

[@scottloewke5199]

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.

[@hail_sagan2830]

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.

[@anuragtiwari3032]

You deserve atleast 1million subscribers !!!

[@AlgosWithMichael]

Thank you!!!

[@nomnomnam]

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.

[@isaiahparker6170]

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?

[@esraaqandeel8465]

Thanks a lot for the animation and code walkthrough!

[@AlgosWithMichael]

No worries!

[@staticFool]

thank you so much man, for the explanation and code walk-through.

[@AlgosWithMichael]

Glad it helped!

[@codingessential91]

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

[@AlgosWithMichael]

I appreciate it! I don't do it for the subs, but more subs would be great haha

[@AloneMaru]

Great explanation and visuals!

[@chrisfair9228]

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?

[@AlgosWithMichael]

Hold control and click :)

[@madhuravp]

Great explanation! i was able to solve it by just looking at your algo explanation!

[@AlgosWithMichael]

That's awesome! nice job

[@juliahuanlingtong6757]

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!

[@AlgosWithMichael]

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!

[@QuOUseTERSEa]

finally I understand, thank you so much!

[@AlgosWithMichael]

Glad it helped!

[@kapilrules]

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

[@kushagrakulshrestha2966]

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 😃

[@GSgurusarath1]

Best video for this problem

[@AlgosWithMichael]

Thank you!

[@cavi8779]

Really appreciate your effort bro...specially that animation

[@AlgosWithMichael]

Thank you so much 😀

[@IbrahimBratan]

Thank you so much !!

[@firstjm9071]

Great animations! :)

[@AlgosWithMichael]

Thanks! 😄

[@therishabhdhiman]

Thanks bro. I love you.

[@joshithmurthy6209]

love the explaination , thanks

[@AlgosWithMichael]

Thank you

[@juan2thepaab]

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?

[@AlgosWithMichael]

If you do enough recursive BT problems, you will get experience solving them with subtle nuances. This question definitely is harder than most though

[@prashantgupta6160]

thanks for awesome video

[@sambasivareddyasam5712]

Thank you so much dude.

[@AlgosWithMichael]

No problem!

[@sudharsansathiamoorthy1075]

Nice explanation!! Keep rocking Bro!!!

[@AlgosWithMichael]

Thank you!

[@mohitpatil1430]

It was really helpful brother Thanks !

[@AlgosWithMichael]

Anytime

[@deluxebigmac]

Thanks, this helped a ton!

[@AlgosWithMichael]

Glad it helped!

[@mylittlepurpleworld]

thanks... really helpful

[@sanjubaloria2745]

Mind blowing animation video bro

[@AlgosWithMichael]

Thank you so much 😀

[@aniketchurihar7394]

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?

[@MrX-zf5gl]

That's why we initialise max is -inf and not zero

[@275phuongvy]

great explanation. Thank you

[@AlgosWithMichael]

You are welcome!

[@dylanshine4263]

Great explanation!

[@AlgosWithMichael]

Thanks!

[@abdelmalek9004]

for the code, how it can be memorized ?

[@vinprabhu]

Good explanation as always

[@AlgosWithMichael]

I appreciate that!

[@LeHoangTu]

Nicely done!

[@AlgosWithMichael]

Thanks!

[@vabiohandoko5679]

I just don't understand how it started from the bottom of the tree based on the code? Can anybody explain it to me?

[@AlgosWithMichael]

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.

[@gauravbhattacharjee4379]

This is gold

[@AlgosWithMichael]

Thanks!

[@kaleemullahnizamani7436]

10:40 why is this Math.max used? i can't understand the reason

[@AlgosWithMichael]

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

[@eddanapudir]

Thanks for the video. Still not clear why it should be rounded to 0.

[@eddanapudir]

I meant at 5:12

[@AlgosWithMichael]

We round to zero because if we return a negative number, the max sum can only get smaller.

[@Garensonic]

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

[@AlgosWithMichael]

Best of luck to you!

[@heisenberg1844]

Amazed.

[@AlgosWithMichael]

Haha thank you

[@raahim88991]

perfectt

[@AlgosWithMichael]

Thanks!