Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@AnnieBox]

Q: we only need to get the max sum WITH split, and we already update it inside of the dfs, then why we still need to return the max sum WITHOUT split from the dfs?

[@kippesolo8941]

i wonder how this works with negative values, shouldnt "leftMax = max(leftMax, 0)" turn any negative number into 0 ?

[@kippesolo8941]

@@AnnieBox how do you think we update leftMax and rightMax then?

[@bowenli5886]

When I search for an explanation, yours would always be my first choice, even though I don't use python, the way you explain each problem is just informative and enlightening, thank you!

[@shaikdiary]

+1. I use Java, but i watch your videos for logical solution and then implement in java on my own (or watch other Java solution videos to refer the implementation details)

[@hitarthdaxeshbhaikothari1688]

Yes, same! I use C++ but always come for explanation here :)

[@ShivamKumar-qv6em]

@@hitarthdaxeshbhaikothari1688 same here bro .

[@mingjuhe1514]

+1 this is a very good channel.

[@sagivalia5041]

I find it a great way to understand it by translating his Python code to the language I use

[@numberonep5404]

a version without the global variable res (it worked for me at least): class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: def dfs(root): if not root: return 0, float("-inf") left, wl = dfs(root.left) left = max(left,0) right, wr = dfs(root.right) right = max(right,0) res = max(wl, wr, root.val+left+right) return root.val+max(left,right) , res return dfs(root)[1]

[@PhanNghia-fk5rv]

did u handle the case where root.val > root.val + max(left, right) ?

[@aleksey3231]

gj man. The code is indeed concise and beautiful

[@haha-hs7yf]

What does wl and wr stand for?

[@numberonep5404]

@@haha-hs7yf no clue sorry, i think i like the letter w for some reason, maybe weight_left/right?

[@supercarpro]

Mate if it wasn't for your vids I'd be so lost. Was able to do this hard problem on my own today after studying your vids for months. I haven't tried it since 4 months ago but was easily able to come to the solution after learning your patterns. This was just a postorder traversal. Thanks

[@nachiket9857]

Here's using nonlocal and also not having to check leftMax and rightMax twice for 0 class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: res = root.val def traverse(node): if not node: return 0 leftMax = traverse(node.left) rightMax = traverse(node.right) nonlocal res res = max(res, node.val + leftMax + rightMax) return max(0, node.val + max(leftMax, rightMax)) traverse(root) return res

[@moto.kartik]

This is the best explanation for this problem I've ever seen. I struggled so much with wrapping my head around the solution in CTCI. Yours makes so much more sense, I wasn't even all the way through your explanation, but was still able to use what I learnt from it to code this up quickly on Leetcode. Thank you man, you're a legend!

[@michaelmarchese5865]

For some reason, I find it more intuitive to only use max() for selecting the largest choice, rather than also using it to coerce negatives to zero: def maxPathSum(self, root: Optional[TreeNode]) -> int: def maxLeg(root: Optional[TreeNode]) -> int: nonlocal max_path if not root: return 0 l = maxLeg(root.left) r = maxLeg(root.right) p = root.val max_leg = max(p, p + l, p + r) max_path = max(max_path, max_leg, p + l + r) return max_leg max_path = -1001 maxLeg(root) return max_path

[@katzy687]

I've noticed you tend to do that list by reference trick for primitive values. Python also has built in way to do that, you can declare the variable normally, and then inside the DFS, do "nonlocal" res. def max_path_sum(root): res = root.val def dfs(node): nonlocal res if not node: return 0 etc.....

[@quirkyquester]

great to know! thx!

[@Nick-kb2jc]

Thank you so much for this explanation. I don't know who comes up with these Leetcode problems but this problem was so damn confusing. Leetcode doesn't provide enough example inputs/outputs for Hard problems like this. I had no idea what was defined as a "path" and it was so frustrating because I was running the solution code and still not understanding why I was getting certain values.

[@zl7460]

Exactly. I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.

[@Grawlix99]

BTW, you can directly plug in '0' as an option when returning from the recursive function. In that case, you only need two or three 'max()' operations, not four: class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: self.res = root.val def dfs(node): if not node: return 0 right = dfs(node.right) left = dfs(node.left) self.res = max(self.res, node.val + left + right) return max(node.val + max(left, right), 0) # Alternate return statement: # return max(node.val+left, node.val+right, 0) dfs(root) return self.res

[@nehascorpion]

Very well explained! I love your videos so much. Your channel is my first resort when I am stuck with complex algorithms. Even the Leetcode solutions are not this simple to understand. Thank you so so much! :)

[@srinadhp]

Spent so much time on this problem to understand the problem statement.. yours is by far the best explanation on what is expected of the problem and how to solve it as well. The idea of splits and why we should send 0 is very helpful to understand. Lots of appreciations! Keep up the good work! You are helping a lot!!

[@Nick-kb2jc]

Dude, same here. I hated this problem.

[@mohamedhabibjaouadi3933]

Thank you for the wonderful content. My question is why going with the array syntax for res, it would be simpler syntactically to use a normal variable. The Javascript equivalent, note that functions mutate global variables (wouldn't recommend it but it works): let res = 0 const dfs = (root) => { if (!root){ return 0 } let leftMax = dfs(root.left) let rightMax = dfs(root.right) leftMax = Math.max(0, leftMax) rightMax = Math.max(0, rightMax) res = Math.max(res, root.val + leftMax + rightMax) return root.val + Math.max(leftMax, rightMax) } const maxPathSum = (root) => { res = root.val dfs(root) return res };

[@japarjarkynbyek8494]

Try to run exact code in Python. You get error because you gonna change that "res" is not defined in that sub function I guess or you cannot mutate global primitive value

[@siqb]

Thank you so much for this brilliant explanation. One tiny remark: Perhaps using a "nonlocal res" in the dfs() function and saving the direct sum instead of a list might have been more clean.

[@dongdongchen455]

how to do that?

[@zhengzuo5118]

How to do that? I can’t use a single variable for res because it always gives an error

[@sagarpotnis1215]

@@dongdongchen455 in the dfs function at the top just define 'nonlocal res' at the top

[@linli7049]

I am totally stunned by this solution. You are so amazing.

[@souparnomajumder]

def dfs(node): if not node: return 0, float("-inf") left, left_max = dfs(node.left) right, right_max = dfs(node.right) return max(node.val, node.val + max(left, right)), \ max(node.val, node.val + max(left, right, left + right), left_max, right_max) _, max_val = dfs(root) return max_val

[@ujjawalpanchal]

Why is your `res = [root.val]` as opposed to `res = root.val`? Why make it a list?

[@KeyAndLock77]

Awesome explanation. I solved but took some times and mistakes but what I learned is that if you don't solve problem on paper, don't code it. You are likely to go towards a dead end in 45 minute interview. Better solve it fully on the paper with all edge cases and then coding is like 5 minutes

[@minh1391993]

can't believe that actually solved that many problem and upload the explanation to KZbin :D . Currently, start my leetcode prac and found your channel here. Amazing work.

[@themagickalmagickman]

I actually solved this one on my one, granted its one of the easier hard problems (and my code ran pretty slow, beat 28%). However, I originally misinterpreted the question as find the max subtree, not path. Luckily it was literally one line of code difference between the two problems the way I solved it, but its a good reminder to make sure you really understand what is being asked.

[@gaaligadu148]

Highly underrated channel! Much Appreciated Content !

[@NeetCode]

Glad it's helpful!

[@AnkitaNallana]

So in the end, it came down to split at that node or no-split and continue down a path (determined by max(leftMax, rightMax)) -- Took me a while but yes, it's so much easier to understand after

[@cavinkumaranmahalingam7570]

Hi, my concern is "How am i supposed to come with such logics when I'm given such problems in any interview?". If you got anything other than "Through practice !" , then I would love to know ; )

[@ObtecularPk]

yeah there is no way i'm solving this in 45 minutes interview question ...

[@hardikjoshi8111]

Another way to conceptualise what constitutes a path is to only have those nodes or vertices in consideration that have at most 2 edges.

[@omarllama]

You can simply use self.res instead of res = []. The self object is there for a reason.

[@Rob-147]

This one really confused me. Thanks so much for your explanation.

[@yu-jencheng556]

Your explanation is so brilliant and clear so that it seems like this is a medium or even easy problem instead of hard! Really appreciate your work and I really think Leetcode should use your solutions whenever possible!

[@bulioh]

In case this helps things 'click' for anyone, I realized this is really similar to Maximum Subarray. In fact if the tree had no splits (were just a linked list) it would be the same algo. But since the tree _can_ split, it just means we have _two_ running sums to look at instead of one.

[@kartiksoni825]

BRILLIANT explanation, thank you Neetcode!

[@yunierperez2680]

Excellent explanation thanks! Just curios why 'res' needs to be an array if you are only using the 0 index, is this a python thing?

[@michaelmarchese5865]

In python, you can read a variable from a higher scope (meaning from outside the function) without a problem. But if you try to modify that variable, it'll think you are trying to create a new local variable, leading to exceptions/bugs. To modify the preexisting variable from outside the function, you need to use the nonlocal keyword. For some reason, neetcode guy decided to avoid nonlocal in favor of a hack. He uses a list for his higher-scoped variable because then he can store the actual value inside of it and modify that rather than the list itself, avoiding the issues I mentioned above. But don't do this. Use nonlocal. In addition to nonlocal, there is a global keyward that does the same but for globals. Neetcode refers to res as a global variable, but it's not. It belongs to the outer function.

[@bloodfiredrake7259]

What is all the values are negatives?

[@ShivamKumar-qv6em]

Nice explanation . Very helpful . The way of explaining through diagram makes the things crystal clear .

[@aybarskeremtaskan]

Shouldn't we return max (dfs(root), res[0]) as the result (it could be the case that either left or right path is negative)?

[@beonthego8725]

The question says , the path does not need to pass through the root.

[@arnobpl]

"The path does not need to pass through the root" sounds like a flexibility but not a constrain. Otherwise, it should say, "the path must not pass through the root." I am confused with the same thing. I tested the code in both ways and both pass all the test cases.

[@arnobpl]

Anyway, I understood why max(dfs(root), res[0]) is not needed. It is nothing related to "the path does not need to pass through the root". In fact, in Example 1, the max path does pass through the root (2+1+3=6). It is because: think about the dfs call when root.val is the actual root of the tree. In line 22, both leftMax and rightMax are non-zeros due to line 16-17, so we are also considering either left or right path being negative. That is why we do not need max(dfs(root), res[0]). That is redundant.

[@mingjunma293]

thx!! But I have a question. Why we use the array to store the final result?

[@wilsonwang8641]

@Caleb Rigg explains this well below

[@chaengsaltz829]

Wow! You're the master! Thanks for sharing!

[@yamaan93]

I'm a little confused as to how the result gets updated to include conditions where you don't split. ie, we never really check for cases where we only take a path 1 way if that maxes sense

[@beonthego8725]

The question says , the path does not need to pass through the root

[@quirkyquester]

the trick lies in max(leftmax, 0), max(rightMax, 0), what these did is to eliminate the left right sub single path if they are < 0. now we get to line max(root.val + leftMax + rightMax) is actually considering all cases when its only root.val, or (root.val + left path only), or (root.val + right path only), or (root.val + left + right). this is why, if this doesn't make sense, read my first line again, they are linked.

[@rakeshkashyap84]

Best explanation. Downgraded the question to Medium level. Thank you!

[@m_jdm357]

All leetcode problems should be like this

[@JaiSagar7]

Awesome explaination of the problem with the optimised solution approach 🔥🔥

[@ancai5498]

Here is the cpp version with code explanation: int res = INT_MIN; int maxPathSum(TreeNode* root) { dfs(root); return res; } // return max value through current node // max value either comes from: // 1. split at current node; // 2. split through parent node, max value current node could provide. int dfs(TreeNode *node) { if (!node) { return 0; } int left = dfs(node->left); left = max(left, 0); int right = dfs(node->right); right = max(right, 0); // split at current node. res = max(res, node->val + left + right); // not split to parent level, max value current node could provide return node->val + max(left, right); }

[@rentianxiang92]

requesting more interview problems, thank you as always

[@SomeThinkingOFF]

explained so smoothly!!!👌👌👌

[@KhoaLe-oc6xl]

This problem should be marked "Easy with Leetcode video" lol. Thank you for making things so comprehensive !

[@numberonep5404]

Lovely content btw, i can't believe how simple u make it

[@mohithadiyal6083]

How can be space complexity be O(h) we aren't using any extra memory ,are we?

[@NeetCode]

Good question, the memory comes from the recursion call stack.

[@mohithadiyal6083]

@@NeetCode thank you 😁

[@RS-vu4nn]

In other languages you can use static variable inside the function instead of global variable

[@colin398]

or an instance variable, anything works either way its not actually global just outsidd the scope of the inner method

[@roman_mf]

Another banger of a solution. I was so close, yet so far :')

[@maryamlarijani5550]

Great explanation! may talk about time complexity too.

[@embarrassed_dodo]

Since n can be upto 3*10^4, how we are using recursion to solve this isn't python has callstack limit of 1000?

[@sachinwalunjakar8854]

Thanks for making such great content for learning, I have one question "how much time you require to solve hard question like this ?"

[@Igloo683]

Instead of using res array we can use self.res.

[@tarek7451]

What's the best way to solve without using the global variable?

[@Saralcfc]

Return tuple of values (max_path_without_splitting, max_path_with_splitting)

[@monicawang8447]

heyy quick confirmation question: I notice that the dfs function has return statement after we update res[0], but this very last value that's returned didn't get used, does it mean it's for the root to pass to its parent? (but since it's already the root, it won't pass it further, so we just ignore it? Thank uu!! really love ur videos!!

[@NeetCode]

Yup thats exactly correct! and thanks for the kind words

[@monicawang8447]

@@NeetCode Heyy NeetCode, I was doing this problem again and noticed that you used 'res' as an array whereas I just used it as a variable. However, when everything else stays the same, it gives scope error and I had to add "nonlocal res" in the dfs function. I'm confused that both methods are changing 'res' in the inner function, but why does your method not need "nonlocal"?

[@johns3641]

@@monicawang8447 You can modify lists, sets, dictionaries that are initiated outside of the function but you can't do that with strings/ints (which sounds like what you did at the end). Because you set res as an integer instead of a list, you have to add the words nonlocal for python to know that it has to modify the variable outside of the dfs function. Just a python quirk, hope that helps

[@nachiket9857]

Returning the value of the actual root would assume that the path traverses through root, so it could be solution to a problem which has that constraint I believe (for anyone reading this later)

[@eamonmahon6622]

Great solution and video! Why does using a list for the res make modifying it within the recursive function easier?

[@howheels]

It's not really "easier" but it avoids having to specify "nonlocal" inside the dfs function. IMHO using a list for res is not as intuitive, but you save a whopping 1 line of code.

[@sankhadip_roy]

why he have used a list for the res , why not just a integer? can anyone make me understand please!

[@angelinazhou667]

Using a list for the res allows us to update the result within the helper function. If res was instead simply a variable that stores an integer, when we try to update it within the helper function, it will create a new variable called res local to the helper function. We use a list to get around this problem or you could alternatively use a variable with the nonlocal keyword

[@sankhadip_roy]

@@angelinazhou667 yes Or can use a class variable using self

[@mehull408]

Amazing explanation ❤

[@ilanaizelman3993]

This is gold.

[@edwardteach2]

U a God. I thought I had to implement dp somewhere, but glad I didn't! Thanks!

[@edwardteach2]

Python implementation: class Solution(object): def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ self.ans = float('-inf') def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) left = max(left, 0) right = max(right, 0) self.ans = max(self.ans, root.val + left + right) return root.val + max(left, right) dfs(root) return self.ans

[@begula_chan]

Thank you very much!

[@chelsylan8554]

very clear! thank you!

[@thevagabond85yt]

3:17 "this(implying 2+1+3+5) is obviously the maximum we can create" BUT NO the right sub tree 4+3+5 =12 is the max sum path.

[@anandkrishnan72]

such an amazing video.

[@hwang1607]

good solution thank you

[@Kenspectacle]

I don't understand, why do you need to make res into a list?

[@MrSaurus]

I am still confused about line 24. Can anyone explain to me how it works?

[@justincao7356]

thank you! Hope this one like and a comment support the channel!

[@onlineservicecom]

Could you give the time complexity and space complexity ?

[@noumaaaan]

I just paused the video to write a comment here to say that I feel like I've watched so much of your content, at this point it just feels like I'm talking to you lol.

[@farazahmed7]

koi company nikaali wikaali?

[@MySWESpace]

Do you have a github link with your code solutions? Your explanations are amazing!

[@mehershrishtinigam5449]

What is the time complexity ?

[@mitchellhuang5488]

Such a clean and clear explanation!

[@yashshukla1637]

- **Introduction**: - Solving the *Binary Tree Maximum Path Sum* problem from the Blind 75 list on Leetcode. - A **path** is defined as a sequence of nodes where each pair of adjacent nodes is connected by an edge, and nodes appear at most once. - **Path sum** is the sum of the node values in the path; negative values are possible, which may affect the sum. - **Understanding Paths**: - A path can go through left and right subtrees but only splits once. - **Max path sum** must avoid adding negative values when possible, but may include them if advantageous. - When traversing, choose the **larger** value of a node’s subtrees to maximize the path sum. - **Brute Force and Optimization**: - A brute force approach would consider each node as the topmost and evaluate subtrees recursively. - Use a **depth-first search (DFS)** to solve subproblems first and reuse results, leading to a **linear time solution**. - **Recursive DFS Approach**: - Starting at the root, recursively compute the max path sum without splitting for both left and right subtrees. - The **max path sum** at each node is the root value plus the greater of its left or right subtree (if no split). - **Global variable** tracks the maximum path sum encountered during the traversal. - **Edge Cases**: - For trees with negative values, nodes can be **excluded** from the path by considering a 0 instead of adding negative values. - The solution works in **O(n) time complexity** and **O(log n) memory** for balanced trees. - **Code Explanation**: - The solution involves a DFS traversal where the **global result** is updated whenever a new max path sum is found. - Recursive returns include the max path sum for **one direction** (left or right) to avoid splitting more than once.

[@mama1990ish]

Keep sharing new videos ! Your videos are awesome :)

[@AnnieBox]

nice and neat explanation!! 👍

[@heisenberg1844]

Amazed.

[@tomarintomarin9520]

Ok let's write some more neetcode if you says so

[@telnet8674]

I was expecting an implementation kinda similar to the house robber III prob lem

[@herdata_eo4492]

why do we need computations for path sum with split then? someone please enlighten me on this 😮‍💨

[@rishab9293]

Reminds me of Kadane's algorithm

[@disha4545]

Can anyone explain why he used res[0], why not just use res, not make it a list since the start declaration ?

[@shivansh-gup]

global variable declaration i think. ChatGPT suggested this.

[@symbol767]

Thanks man

[@radishanim]

you can just use `self.res` instead of [res] to modify the value globally. using the properties of a list to achieve this might be seen as a little hacky by the interviewer.

[@veliea5160]

leftMax is a node, how come `max(leftMax,0)` returns a value?

[@avenged7ex]

LeftMax isn't a node, it is the returned value from the dfs() call which is passed the node as a parameter. The code runs recursively until the node is determined to be null (meaning we've reached the end of the tree) and return 0. At the bottom of the recursion stack we calculate the max values between this new 0 value and the value of the leaf node, and return a maximum value (see how we just returned the max? this is the integer value leftNode is assigned). Now the recursion calls begin to finish, all-the-while passing the previous maximums to the leftMax and rightMax variables.

[@albertjtyeh53]

general question, when analyzing trees, often you are calculating something recursively, is that considered overlapping subproblems or not? and are binary trees considered inherently optimal substructures? or not. thanks! btw love your videos and subbed!

[@tejeshreddy6252]

Hey, not sure if you still need the answer but here goes... Generally with a tree all nodes are unique so there are no sub-problems like in fibonacci series etc. In the latter case, we have non-unique nodes such as 2, 3, 5 which we have to traverse again to get to the bigger solution

[@emmatime2016]

You are just great!

[@NitinPatelIndia]

Great explanation! Thank you so much.

[@rishabhverma3615]

Can someone explain the concept of adding 0 while updating leftMax and rightMax?

[@SandeepKumar16]

The idea behind comparing with 0 is - We don't want to add up negative numbers in the path. Because that would decrease the sum. So we compare with 0. If leftMax is negative, max(leftMax, 0) with give 0. Adding 0 to the result will not effect the result.

[@NapoleonNol]

so why does the list for res allow it to be changed in the function?

[@minyoungan9515]

@Nolan were you able to figure it out?

[@avenged7ex]

@@minyoungan9515 In Python, lists are a mutable object, while primitive type assignments are not (You can think about this like saying lists are always passed by reference, and objects like integers are not). So by passing a list containing a value, the reference to the list isn't lost, yet we're able to change the value inside of it. Another work-around would be to declare the result within the object, where it can be referenced using self.res . Another choice would be to define res outside of the dfs() function, and then define it again within the function using the nonlocal keyword.

[@minyoungan9515]

@@avenged7ex Thanks for the explanation :) That makes sense

[@satadhi]

can you guys explain why the res is list instead of a simple variable

[@avenged7ex]

simple variables are immutable (think of this as passed by value), whereas, lists are mutable (passed by reference). In order to change the value of the result, he's wrapped it in a list so that the reference to the answer is never lost, while allowing him to alter the value within the lists contents. Another work around would be to declare the res variable as an instance of the Solution class (self.res). Or by declaring it outside the dfs() function, and also within it using the keyword nonlocal (i.e. nonlocal res).

[@Ifeelphat]

@@avenged7ex interesting so was the list used to improve performance?

[@avenged7ex]

@@Ifeelphat no, it was used to increase readability

[@saugatkarki3169]

it shows UnboundLocalError when a simple variable is used instead of a list. that's what it did for me.

[@liamsism]

@@avenged7ex tuples are immutable too but it works with them.

[@darrylbrian]

why make the global variable - res - an array with one item? why not just set the value to the item itself? we never push or append anything else to it. just curious, thank you for all that you've done.

[@VipulDessaiBadGAMERbaD]

it works even if its not used as array, actually it should be just a simple variable

[@nisusrk]

What if all the nodes are negative?

[@avenged7ex]

This is handled by always including the current node's value in the max() calls. The result variable would be assigned to the largest individual node value in that case, as it is always included in any max() call.

[@joshithmurthy6209]

I first tried to solve the question without considering the single path and later I realized it is not allowed

[@garciamenesesbrayan]

why global would be considered as cheating?

[@gazijarin8866]

God's work

[@anantmittal522]

Can anyone provide O(n^2) solution to this problem ?

[@asrahussain8642]

this is kinda like house robber 3

[@nithingowda1060]

can anyone tell me time and space complexicity please?

[@soukaryasaha3825]

could someone explain how to do this without the global variable

[@Rob-147]

I did it using a pair of in c++. code is below /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: pair dfs(TreeNode* root) { if (!root) return make_pair(0,INT_MIN); pair left = dfs(root->left); pair right = dfs(root->right); int currPath = root->val + max(max(left.first,0), max(right.first,0)); int currMaxPath = root->val + max(left.first,0) + max(right.first,0); int maxPath = max(max(left.second,right.second), currMaxPath); return make_pair(currPath, maxPath); } public: int maxPathSum(TreeNode* root) { pair result = dfs(root); return result.second; } };

[@ameynaik2743]

Great video, is there a github location where I can find all your codes?

[@TechOnScreen]

yes.. navigate to this url github.com/neetcode-gh/leetcode