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

Binary Tree Maximum Path Sum is a popular LeetCode problem involving the knowledge of recursion, binary trees, and postorder traversal. This problem is asking at companies including Amazon, Google, Microsoft, Facebook, and Bloomberg.
For this problem, we are given a binary tree and must find the maximum path sum in the tree. A path sum is the sum of the values in a path of the binary tree. The binary tree can have negative numbers, thus our maximum does not necessarily have to be positive. To solve this efficiently, we must traverse each node in the tree computing the max sum at each step. If we encounter a negative number, we will bound that value to a zero to ensure that we always get the absolute maximum.
The time complexity of the solution will be linear because we must does each node in the tree in our traversal. The space complexity is going to be O(H) where H is the height of our tree. Since we are using recursion, in the worst case, we will have H recursive calls which will fill up our stack space.
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🔗 Social 🔗
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
⭐️ Timestamps ⭐️
00:00 - Intro
00:19 - Problem Overview
02:22 - Algorithm Walkthrough
07:35 - Code Walkthrough
10:52 - Time & Space Complexity

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

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

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

[@iRockTheBeat1]

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

[@mpedzi031]

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

[@xujia1001]

Crystal clear. You rock it!

[@IChowdhury01]

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

[@AlgosWithMichael]

No problem, glad it was helpful for you!

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

[@ALEXANDER6888]

Your explanation was Godlike! Thank you very much!

[@puneethj9920]

Best explanation on youtube with good animation thank you man!

[@AlgosWithMichael]

Wow, thanks!

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

[@ruthylevi9804]

best explanation on this - thank you!

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

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

[@nipnip9400]

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

[@terrencecrawford3308]

SO TRUE!

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

[@Shellyanne5]

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

[@AlgosWithMichael]

Say hi to roo

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

[@edgargranados1676]

Michael has the best explanation videos!

[@AlgosWithMichael]

Glad you like them!

[@therollingambit5222]

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

[@ajaib1313]

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

[@AloneMaru]

Great explanation and visuals!

[@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 👍🏻☺️

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

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

[@supax2]

You're awesome man. Keep it up!

[@AlgosWithMichael]

Appreciate it!

[@IbrahimBratan]

Thank you so much !!

[@esraaqandeel8465]

Thanks a lot for the animation and code walkthrough!

[@AlgosWithMichael]

No worries!

[@QuOUseTERSEa]

finally I understand, thank you so much!

[@AlgosWithMichael]

Glad it helped!

[@manikantareddy2256]

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

[@AlgosWithMichael]

Glad it helped!

[@deluxebigmac]

Thanks, this helped a ton!

[@AlgosWithMichael]

Glad it helped!

[@madhuravp]

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

[@AlgosWithMichael]

That's awesome! nice job

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

[@joshithmurthy6209]

love the explaination , thanks

[@AlgosWithMichael]

Thank you

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

[@mylittlepurpleworld]

thanks... really helpful

[@therishabhdhiman]

Thanks bro. I love you.

[@prashantgupta6160]

thanks for awesome video

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

[@aakashshivanshu3578]

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

[@AlgosWithMichael]

Happy to help!

[@mohitpatil1430]

It was really helpful brother Thanks !

[@AlgosWithMichael]

Anytime

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

[@GSgurusarath1]

Best video for this problem

[@AlgosWithMichael]

Thank you!

[@cavi8779]

Really appreciate your effort bro...specially that animation

[@AlgosWithMichael]

Thank you so much 😀

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

[@275phuongvy]

great explanation. Thank you

[@AlgosWithMichael]

You are welcome!

[@LeHoangTu]

Nicely done!

[@AlgosWithMichael]

Thanks!

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

[@sudharsansathiamoorthy1075]

Nice explanation!! Keep rocking Bro!!!

[@AlgosWithMichael]

Thank you!

[@dylanshine4263]

Great explanation!

[@AlgosWithMichael]

Thanks!

[@terrencecrawford3308]

Michael is the CEO of being epic!

[@nipnip9400]

Accurate

[@bibiworm]

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.

[@anuragtiwari3032]

You deserve atleast 1million subscribers !!!

[@AlgosWithMichael]

Thank you!!!

[@6969MrBreast]

consider a tree as follows: 1 / \ -10 -10 the above code returns 1 as answer however the shortest path should be -9 as a single node cannot be a path

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

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

[@vinprabhu]

Good explanation as always

[@AlgosWithMichael]

I appreciate that!

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

[@sanjubaloria2745]

Mind blowing animation video bro

[@AlgosWithMichael]

Thank you so much 😀

[@gauravbhattacharjee4379]

This is gold

[@AlgosWithMichael]

Thanks!

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

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

[@heisenberg1844]

Amazed.

[@AlgosWithMichael]

Haha thank you

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

[@abdelmalek9004]

for the code, how it can be memorized ?

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

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

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

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

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

[@raahim88991]

perfectt

[@AlgosWithMichael]

Thanks!

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

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