LeetCode 124. Binary Tree Maximum Path Sum (Algorithm Explained)

[@haoshenyu]

//this is Post Order Traversal, goes from bottom up to the top //for max_path_sum, we add all positive values of left subtree,right subtree and root and find the maximum //for the result of method pathSum, we return only the larger sum path from bottom up, either the left or the right, because from a subroot you can only choose one direction to sum

[@evgeni-nabokov]

Why don't you explain why you get a max(0, left/right)? You are just repeating after what you are typing. Is this called "algorithm explained"? Same question to the return value.

[@leomonz]

I think 0 just avoid getting negative number... he didn't explain it.

[@tarsala1995]

The reason for max(0, left/right) is because we don't want to decrease our current solution. If the left subtree is less than 0, then it only makes our solution worse, therefore its better to start from beggining (0). The last statement is for choosing better sum from tree. We have to have a path (not sum of paths) so the greater value the better

[@pauljustin9583]

​@@tarsala1995 A single node can form the answer. When all numbers are negative except one, then that non-negative node should be the answer. If all numbers are negative then the biggest of them all should form the answer. This 0 is taking care of those cases. Precisely the next statement where the actual global answer is getting updated. Although this is a poor explanation for this problem, when he went "boom, boom, boom", my head went "fuq, fuq, fuq".

[@wolfroma123]

Problem is good, explanation could be better though.

[@jennaalden3658]

"its easy what more do I need to explain to you?" does not a good teacher make.

[@vroomerlifts]

These videos are made after you atleast attempt a question, not to learn a question.

[@aatifnazar1766]

Thats a good problem. Normally we dont traverse like this, i mean updating one local max and one global max at the same time is kind of new for me. Great solution. Opens a new way of looking at tree traversals.

[@priyanshu.tiwari]

yeah same for me. Brilliant approach

[@psn999100]

Thanks Nick. I tried this without watching the solution, and kept getting errors because of the possible negative numbers in the nodes. I think the key piece of code is in line numbers 20 and 21. Since we take a max of 0 and left or right subtree values, we effectively discard any -ve numbers (because they can never make an even bigger path val). Without these max functions in line 20 and 21, this would work just fine for all BT with nodes as positive values. In fact the original interview question is to assume that all nodes have positive values and then the interviewer asks you to modify your code if there were negative numbers. The recursion and all the other calculations can be thought of in 10 mins assuming the candidate has a good grasp at recursion and graph traversals.

[@tvishathakur8947]

Me too! I also kept getting wrong answers for that but still didn't quite understand why does that work when we take max of 0 and right/left sub-tree. What if all the nodes are negative? :(

[@psn999100]

@@tvishathakur8947 you can draw out a tree and see why taking 0 is better than including a -ve number in your max path sum.. a -ve number can never increase a path sum. If all numbers are negative, then you need to ask the interviwer what should you return. Those are good clarifying questions actually !

[@tvishathakur8947]

@@psn999100 Yes now I understood! So here in case of negative values it returns the root value. Thankyou! :)

[@Garensonic]

I was asked this same question in my Amazon onsite 5 years ago and could not figure out the code that was actually updating the max path sum at the time

[@ocoocososococosooooosoococoso]

so funny when ur say "fun things going in this recursive function" and second later "I don't even know what I'm saying" LOL

[@mikami5799]

i dont get it, what if the root node is positive values? wouldnt this solution be 9+root+42? and how could this answer be possible if no U turn is allowed for paths?

[@mohit_talniya]

What if all the Nodes have negative values? You are discarding negative values.

[@Cvarier-channel]

No, the algo would just return the negative value closest to 0.

[@jeremycohn9992]

I'm glad you pointed out there's no backtracking. The original problem didn't say that, but its obvious from the solution that this is the case.

[@moonman239]

so basically we look at any conceivable path in the binary tree, and the maximum sum of all possible paths is the answer?

[@sergekov3804]

the max space Is O(log n) as your recursion (stack) will never exceed log n. Before start for every of next to each other subtrees previous stack will be cleaned (not true, comments)

[@AryanKumar-wn1yd]

Not true, in a binary tree the worst- case height is n not log n. Again, WORST CASE height!!

[@prashanttripathi7339]

O(lg n) would be for a balanced binary tree.

[@sergekov3804]

I see. You are right guys. Also, I think that is worth mentioning to the interviewer, the balanced and worst cases.

[@sjy269]

I think you are confused, man.

[@anuragv400]

Solution is good but you are looking too confused man... I think your explanation made it more complicated

[@shubham_only]

Your clap hurted my ear

[@crazytimes564]

"you know what I mean" - no we don;t

[@AruneshSrivastava]

why we need to pass 0 for left and right variables

[@ajinkya90swim]

we compare the with zero because, if we get a negative value from left or right subtree, then we need to just consider the current node in order to maximize the sum. Example : [2 , -1] is your tree, where -1 is the left/right child. If comparison with zero is missing then left = -1, right = 0, curr = 2 , then maxVal = 1, which is wrong. The correct answer is 2. Hence we discard the negative values.

[@deveeshmusic5045]

your other videos are fine, this is one terrible.

[@satyabusi7344]

what was the class that he mentioned. The captions read "walkman with alice videos on algorithms"

[@NaveenKumar-os8dv]

I had problem understand at that return statement

[@AmolGautam]

Thank you.

[@abhinavyel166]

Can anyone help me with why is he returning result and calculating max_path_sum

[@arungiri8560]

The max_path_sum indicates the max sum found overall, and the result is sum for the current node, at a certain node how can you decide that whether you should take the left node, or the right node or sum of all three is your answer. For eg. if the nodes were 15--20--7 then we take the max sum as 15+20+7-->max_path_sum but at this point we don't know this is the max sum for sure, but at this point we know the max sum that can be transferred is 15+20-->max(left,rigth)+current.

[@ramizrizwan3057]

great video

[@zixuanzhang5950]

Great solution! Thanks!

[@ShanuGandhi]

love the way he claps!!!

[@aryanjangra4612]

great solution man, although your explanation was horrible (im sorry P) just looking at your solution and dry running it on a random tree did it for me! maintaining two variables/return in a single function is new for me

[@444not]

You clearly don’t know how it works.

[@iskandaratakhodjaev9479]

He is just writing the code and calling it explanation of the problem.. lol

[@lifehacks9450]

pls uplod unique path 3 problem on leetcode

[@vk1618]

Review

[@aatifnazar8203]

please work on your presentation skills, you seem you are not at all interested, just doing it because someone is forcing you to do

[@biswamohandwari6460]

Man! You look good, talented and to be honest your coding skills are fantastic....

[@acxd]

nick you should also code in C++