I rerecorded this solution since I thought it could be better, please check out this version instead: ruclips.net/video/K81C31ytOZE/видео.html It's half the length and still covers everything. 🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Alternative mathematical approach: It made a little more sense to me to return 0 for a Null node. In doing so, you don't need the + 2 in the updating of the result. You are essentially accounting for the parent edge in different ways. I found this approach to come a little more naturally to me, so I'm posting in case it helps anyone! def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def dfs(root): nonlocal diameter if root is None: return 0 left = dfs(root.left) right = dfs(root.right) diameter = max(left + right, diameter) return max(left, right) + 1
What does the left + right part do exactly, and why is it needed? Im able to follow everything else though, just confused about that and why we are calculating 2 maxes.
This is actually very easy if you don't do the -1 +2 bullshit. All you gotta do is height of left, height of right and return the bigger of the two + 1 (to add current node) in each recursive call. The diameter at each node is then leftHeight + rightHeight Got confused during this video and solved it on my own first try in 5 min
If you are new to Data Structures and don’t understand recursion concept in Trees, don’t worry. I used to be like that until I find this channel sometime ago. White boarding is a must practice to understand Trees. Watch as many videos as possible. Later you can worry about the code. It will be that one snap of a moment you need to wait for to realize that you understood Trees. I had that snap of a moment. Don’t give up. We are Engineers 👩💻 👨💻
I think this problem deserves an update. The way you explained it is pretty complicated. It's way more intuitive to simply count the number of edges. ``` class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: if not root: return 0 diameter = 0 def dfs(node): if not node: return 0 edges_l = dfs(node.left) if node.left else 0 edges_r = dfs(node.right) if node.right else 0 nonlocal diameter diameter = max(diameter, edges_l + edges_r) edges = 1 + max(edges_l, edges_r) return edges dfs(root) return diameter ```
This looks amazing ! I came up with similar solution as Neetcode, but this looks more neat, Good Job! I will credit you when I add this on leetcode. Thanks.
Python makes a copy of the primitive types if you pass them in the function so the value doesn't change outside of the function. He used a non-primitive type (list object) to make changes because a list object is stored on the heap and is pass-by-reference. He could've also made a class variable called self.res= 0 and used it in the function with self.res
@@ruspatel1996 isn't it more like this? if we just use res we are assigning a local variable "res" inside a dfs function so when python interpreter meets "max(res,2+left+right" res doesn't have any value but with res[0] it is not assigning it is actually reading value. so python interpreter will see there is no local variable "res" inside dfs function and move on to outer scope
@@dohyun0047yeah, i thought so too, at least in this case, you actually wouldn't need a mutable variable, a simple res=0 would suffice. Edit: sorry, my mistake, it's a python scope thing, you do need a list, got it.
thank you. The tricky part of this problem is the -1, +1, height, diameter. So many tutorials just take them for granted and offer no explanation, but you did an amazing job talking about the whys. Bags of thanks!
I found this explanation quite difficult to follow, especially around 8:19, when NeetCode starts talking about "convention" to make the math work. The solution works, yes, but I am left a little dissatisfied with the overall explanation as it is still quite unclear. I don't seem to find this convention being used in other problems, but maybe that's because I haven't done enough of them yet.
@@user-ib3ev5pl2t Nobody is expecting the other to think for them, but if something is meant to make things easier, it should make things easier, otherwise what's the point? Clearly this explanation was off and made things difficult.
First of all, thanks for this fantastic channel! However, for this problem I find the following code way easier: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def traversal(root): nonlocal max_d if not root: return 0 left_d = traversal(root.left) right_d = traversal(root.right) max_d = max(left_d + right_d, max_d) return max(left_d, right_d) + 1 max_d = 0 traversal(root) return max_d
This solution was easier for me to understand, thanks. What's the intuition around calculating max_d though? How do you know to use the sum of heights?
@@EE12345 the max diameter of a node is equal to the (max height of left + 1) plus (max height of right +1) - the longest path going through it. however in this solution the +1 is already being incorporated in the return, so defining the height as "the number of edges being given to the parent node". which means that in this solution, height is 0 for null nodes and 1 for childless ones
I felt I could easily get so confused by this tricky -1 counting algo... later I found out another alternative which seems more clear to me is to just use max() to include both cases instead: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: ans = 0 def longestPath(node): if not node: return 0 left = longestPath(node.left) right = longestPath(node.right)
nonlocal ans ans = max(ans, left + right) return max(left, right) + 1 longestPath(root) return ans
The core idea for this issue is pretty much the same as the Hard problem max path sum(lc 124), for a node, we have two options, 1. split 2. no split if we split at the current node, we'll have to calculate the path left -> current-> right. In contrast, if we don't split we'll have to return the max path the current node could return to its parent. Hope it helps
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
@@Incroachment if you use res = 0 . changes inside the function won't affect the original variable outside the function,search for Immutable vs Mutable
res = [0] is no mistake, sure you can initialize it as res = 0 but then you have to use "nonlocal res" to make it accessible inside the helper dfs() function because integer objects are immutable objects ( if you try to modify it inside helper dfs() fucntion without using "nonlocal" the program will create a new object instead of using outer scope object). On the other hand list objects are mutable objects so can modify it anywhere in the program. #maile7853 #Incroachment
Out of so many videos, this is the first time that I think my solution is more clear and self-explained. :). // Notice that when the tree is like a triangle, its maxDiamter is just left tree height plus right tree height. var diameterOfBinaryTree = function (root) { /** * Returns the height of a tree. * A tree with a single node is of height 1. */ function getHeight(cur) { if (!cur) return 0; // The end of tree, height is 0 const leftHeight = getHeight(cur.left); const rightHeight = getHeight(cur.right); const curDiameter = leftHeight + rightHeight; maxDiameter = Math.max(maxDiameter, curDiameter); return 1 + Math.max(leftHeight, rightHeight); } let maxDiameter = 0; getHeight(root); return maxDiameter; };
@@richardyeh718 I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
that is becasue how python's scope works. you cannot modify the variable if it is in outer scope. u can still use a variable but u have to use "nonlocal" keyword before using res inside dfs to let python know that this is in outer scope res=0 def dfs(root): ....... ....... nonlocal res res=max(res,2+left+right)
Also you usually use nonlocal if you want to make that variable global AND you want to modify it. If your not modifying and just looking then you can call it normally without nonlocal
It is in fact necessary to create a list here to store and update the final diameter value. The list in Python is mutable, meaning that you can update/mutate elements of a list whether the list is global or not. If you choose to use a global integer variable, then you always have to declare it is global inside your helper function to update it. Otherwise, you code will throw an error. Oh, and the global variables must be defined outside of the class. Code example below: res = 0 class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def helper(): global res if not root: return -1 left = helper(root.left) right = helper(root.right) res = max(res, 2+left+right) ... You may argue what if we pass res as a helper function's argument like "def helper(res):" and then can we avoid declaring that it is global? The answer is no. When you pass the variable as a function's argument, then it will only create a copy of the global variable that is in a different memory location from the global variable. This will result in keeping the global variable "res" unchanged the whole time. If you want to dig deeper on this, refer to this documentation. www.dataquest.io/blog/tutorial-functions-modify-lists-dictionaries-python/.
I think this solution will be a bit simpler to understand class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def dfs(root): nonlocal res if not root: return 0 left = dfs(root.left) right = dfs(root.right) res = max(res, left + right + 1) return 1 + max(left, right) res = 0 dfs(root) return res - 1
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
I made use of the maximumDepth problem to get the depths of the subtrees of a node, added them to get the diameter wrt a node. Then recursively called the diameter function on the left and right children and returned the max of the three. I felt this made sense to me from understanding standpoint. Putting my code for reference. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: #find the depth of left and right subtree from each node. Sum them to get the diameter wrt that node. #recursively call the same fn on the right and left child to get the same. #return the maximum of the three i.e., current diameter, diameter of right child, diameter of left child. def depth(self, root: Optional[TreeNode]) -> int: if not root: return 0 right = 1 + self.depth(root.right) left = 1 + self.depth(root.left) return max(right,left) def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: if not root: return 0 rightdepth = self.depth(root.right) if root.right else 0 leftdepth = self.depth(root.left) if root.left else 0 dia = rightdepth + leftdepth return max(dia, self.diameterOfBinaryTree(root.right), self.diameterOfBinaryTree(root.left) ) Hope this helps!
For anyone reading this in future, this was my initial attempt too and did help me understand but it is actually O(N^2). Every call of depth will have O(N) complexity and diameterOfBinaryTree will also be called N times as we're calling it on every node.
Great solution💯. Thanks for the explanation. Something I noted about the solution. You set the global variable 'res' to be an array of length 1 instead of using an integer. This has been a problem for me in other recursive questions. Could you explain why an array works as a global variable in recursive questions and not integers? Thank you!
In python land, non-primitive datatypes such as list are passed by value. This makes it possible to update it rather making copy everytime. Hope this helps :)
This is used as a workaround in Python. In Python, inner functions have access to variables in the outer function but they cannot modify them without using a workaround. Due to a quirk of Python's name binding, we can use a mutable object such as a list to bypass this problem. However, it is an awkward workaround and not the 'Pythonic' way to modify outer function variables. The proper convention here is to use nonlocal as shown below: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: res = 0 def dfs(root): nonlocal res if not root: return -1 left = dfs(root.left) right = dfs(root.right) res = max(res, 2 + left + right) return 1 + max(left,right) dfs(root) return res
@@EverydayAwes0me ah yes, the "this technically isn't how the language is supposed to work but we're going to take advantage of its quirks" answer. Bad technique for the workforce.
@@tonyiommisg List can update and store values by avoiding returning something in a helper function. In my habit, sometimes it is a little bit tricky for me to code with return in the helper function.
It's not just about avoiding your bad habit. It is in fact necessary to create a list here to store and update the final diameter value. The list in Python is mutable, meaning that you can update/mutate elements of a list whether the list is global or not. If you choose to use a global integer variable, then you always have to declare it is global inside your helper function to update it. Otherwise, you code will throw an error. Oh, and the global variables must be defined outside of the class. Code example below: res = 0 class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def helper(): global res if not root: return -1 left = helper(root.left) right = helper(root.right) res = max(res, 2+left+right) ... You may argue what if we pass res as a helper function's argument like "def helper(res):" and then can we avoid declaring that it is global? The answer is no. When you pass the variable as a function's argument, then it will only create a copy of the global variable that is in a different memory location from the global variable. This will result in keeping the global variable "res" unchanged the whole time. If you want to dig deeper on this, refer to this documentation. www.dataquest.io/blog/tutorial-functions-modify-lists-dictionaries-python/.
Is there a bug in this at: ruclips.net/video/bkxqA8Rfv04/видео.html ? You say D = L + R + 2, but you add it as D = 1 + -1 + 2 = 1, but shouldn't it be 2?
I tried the same thing. It is something to do with global variables, but I couldn't get it to work with just a standard int. Not sure why setting res to an array makes the difference.
class Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: res = 0 def dfs(root): if not root: return -1 left = dfs(root.left) right = dfs(root.right) nonlocal res res = max(res, 2 + left + right) return 1 + max(left, right) dfs(root) return 0 if res == 0 else res
@@singletmat5172 I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Hey i have a doubt regarding res variable I did very similar one with it, I used variable instead of array but I keepts throwing me local variable reference before assignment could you say what is wrong with it.
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
To avoid the -1 or 0 definition, one can build a graph based on the tree. Finding a path based on a graph is pretty intuitive. The process of building a graph based on a tree is mechanical. So, it is easy after some practice.
Yeah this is true. It's way easier to remember also. Basically two problems for the price of remembering one! var diameterOfBinaryTree = function(root) { let max = 0 dfs(root) return max function dfs(root) { if (root == null) { return null } let left = dfs(root.left) let right = dfs(root.right) max = Math.max(max, left + right) return 1 + Math.max(left, right) } };
inclusion of -1 for empty node makes it complicated: # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: res=0 def dfs(root): nonlocal res if not root: return 0 left=dfs(root.left) right=dfs(root.right) res=max(res, left+right) return 1+max(left,right) dfs(root) return res
The ambiguity of the problem comes from combining the two concepts together. The HEIGHT of the tree AND the longest PATH. Those are not the same. Consider the binary tree: 1 / 2 The height of the tree is 2, but the longest path is 1 (the number of edges). Here is a more explicit solution to the problem in Javascript (it should be pretty similar to the Python code). The variable "d" is not used really, but added to debug the state at the given moment. function diameterOfBinaryTree(root) { let max = 0 function dfs(root) { if (!root) { return [0, 0, 0] } const [,heightLeft, nPathLeft] = dfs(root.left) const [,heightRight, nPathRight] = dfs(root.right) // number of edges const n = (root.left ? 1 : 0) + (root.right ? 1 : 0) const d = n + nPathLeft + nPathRight const h = 1 + Math.max(heightLeft, heightRight) // the longest path const p = h - 1 max = Math.max(max, d) return [d, h, p] } dfs(root) return max }
Same solution as others have pointed out, but with more understandable variable names so you can guess better what is going on: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.diameter = 0 def height(node) -> int: if not node: return 0 left_height = height(node.left) right_height = height(node.right) # Update the diameter if the current path is longer self.diameter = max(self.diameter, left_height + right_height) # Return the maximum height of the current node return max(left_height, right_height) + 1
Hi, I tried with another variable let's say t = 0 and used t at max function -----> this is not working showing as a variable is referred without assignment. But it is working with t= [0]. Could you explain why?
You have to use the nonlocal python keyword to do it that way. Otherwise it thinks you're using a variable local to the function, which hasn't been assigned yet.
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Also you don't have to do -2 operation if you use depth instead of height (I'm not sure if these are two same terms). Then depth of Null-node is 0, and depth of Node with no children is 1 (and so on). So in this way you have to only sum 2 depth. Code here: class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: res = 0 def dfs(root: Optional[TreeNode]): if root is None: return 0 left_depth = dfs(root.left) right_depth = dfs(root.right) nonlocal res res = max(res, left_depth + right_depth) return 1 + max(left_depth, right_depth) dfs(root) return res
Imo -1 makes it more confusing, simply said, if there's 1 node in the left, then diameter to the left = 1, so diameter = height left + height right is more clear in this sense
I think returning -1 and making 2 + left + right makes it more complicated or at least for me. The below is working perfectly fine as well. def dfs(root: Optional[TreeNode]) -> int: if not root: return 0 left = dfs(root.left) right = dfs(root.right) result[0] = max(result[0], left + right) return 1 + max(left, right)
why cannot we define a simple variable to store max but doing it as *res[0]* ? Not able to find answer in the web for this. I know i am missing something related to variables, lists and their behaviour with scopes.
yeah someone asked the same question below, apparently you can't modify a variable when you define it in the outer scope. You can modify elements of a list however, hence the usage of a single element list.
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
Why does he store the solution in the first index of an array? Could he just use a variable? has something to do with being visible inside the scope of the dfs()?
best explaination on recursive functions and binary tree diametre problem , thanks for the video , this video will blow up , ill share this masterpiece with my friends too :)))
U a God, another implementation without the -1 and 2: class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ self.ans = 0 def helper(root): if not root: return 0 left = helper(root.left) right = helper(root.right) self.ans = max(self.ans,left+right) return 1 + max(left,right) helper(root) return self.ans
Why res = [0] and not just res = 0. I tried it like that and got: UnboundLocalError: cannot access local variable 'dia' where it is not associated with a value
Well explained, but I don't think it is intuitive to use the "-1" for an empty Node. Instead, we should do what we have always done for empty nodes; return 0. This would make the code much simpler, as now you can get rid of the "2" and only write "res[0] = max( res[0], left + right )" (which makes more sense imho) And as mention before, this is consistent with how we usually do DFS. I think this small part of the code might have confused a lot of people as to why this problem is "Easy"
Even if we rewrite 2 + left + right and -1 for empty node AS just returning 0 for empty node and doing left + right. It works. That is because in the latter, I am assuming that the height of the leaf node is 1 and not 0 AND height of empty node is 0, which alters the convention that height of leaf node is 0 and height of an empty node is -1. I don't know why they do it only that way when both ways could work I guess. class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: res = [0] def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) res[0] = max(res[0], left + right) return 1 + max(left, right) dfs(root) return res[0]
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Why if the diameter is not starting with root node we are bit adding 1 just adding height of left and right subtree whereas if it's root node we are adding 1 why?????
I just love how the LC introduction to binary trees is really helpful and understandable, then the following questions are like, "Now give me some space-age shit that requires three helper functions".
class Solution(object): def __init__(self): self.max_D = 0 def diameterOfBinaryTree(self, root): self.dfs(root) return self.max_D def dfs(self, node): if not node: return 0 left = self.dfs(node.left) right = self.dfs(node.right) self.max_D = max(self.max_D, left + right) # Update max diameter return 1 + max(left, right) # Return the height of the current node
Love your vids in general but this was just terribly explained. Absolutely awful. It felt like you didn’t even understand it fully and just copied a solution from leetcode. Why is result initiated to an array with value 0. Why not just 0 I somewhat understand the logic for needing height but you made no effort to even discuss its relevance. Why it’s important to distinguish from diameter for example. Also why even set a null node to -1. Set it to 0 and set a non empty one to 1. If the node is non empty then just add 1 Is it really even important to have height ? After watching twice I have no idea Horrid explanation and very disappointed given how nice some of your other videos are. It truly felt like you had no idea what u were talking about
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
what the hell is this problem, I still get lost why left is counted by left = dfs(node.left), I just don't know, there is no counting in the function at all. 😿
Because you cannot modify res inside of a nested function as its a nonlocal variable whereas lists are mutable. If you want to use res you can use nonlocal keyword to declare it inside nested function class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def dfs(root): nonlocal res if not root: return 0 left = dfs(root.left) right = dfs(root.right) res = max(res, left + right + 1) return 1 + max(left, right) res = 0 dfs(root) return res - 1
python scope. Python will look for the variable to mutate starting from the closest scope, and work its way up. The statement res = res + 1 (aka res += 1) it will evaluate from right to left (res + 1). Python will ask what scope is res defined in so I can access it; ah, I see within my scope I have a res =, so I will use that definition. Back to my res + 1, that res hasn't been defined yet (it's defined same line, which is obviously a syntax error), so I will throw. The solution is to define res in the same scope, then within the inner scope tell the python interpreter it should look for the higher scoped definition with non local. So you can do: bar = 1 def foo(x): nonlocal bar bar += 1 With neetcodes solution, you never "redefine" the variable, so it just works. Both solutions are unintuitive, but that's what you get with python :/
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Using a -1 for null nodes is really smart. If you don't do that, your code ends up in if statement hell. How do you come up with these elegant algorithms?
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
This has something to do with making res a global variable. Can someone explain why res=[0] makes it global? Also, if you wanna use res = 0, use the nonlocal keyword, works just as well.
So that we can change or update the values of list (which is declared at global scope) ...from function scope since...list are mutable and pass by reference.
Solved without looking at NeetCode's solution, but came to check if there was some easier hack around the problem since it was labelled "EASY". My solution was better than 92% in time complexity and better than 76% in space complexity. class Solution { public: // return what value should get added to parent // maximum possible diameter at any given is recorded in curr_max variable int func(TreeNode* root, int &curr_max){ if(root == nullptr){ return 0; } else if(root->left == nullptr && root->right == nullptr){ return 0; } else if(root->left != nullptr && root->right == nullptr){ int left_path = 1 + func(root->left, curr_max); if(left_path > curr_max){ curr_max = left_path; } return left_path; } else if(root->left == nullptr && root->right != nullptr){ int right_path = 1 + func(root->right, curr_max); if(right_path > curr_max){ curr_max = right_path; } return right_path; } else{ int left_path = 1 + func(root->left, curr_max); int right_path = 1 + func(root->right, curr_max); int total_path = left_path + right_path; if(total_path > curr_max){ curr_max = total_path; } return max(left_path, right_path); } } int diameterOfBinaryTree(TreeNode* root) { // there will be a current diameter for a path passing through current node // you need to pass on the longer of the subtrees to the parent int curr_max = 0; func(root, curr_max); return curr_max; } };
Can someone please explain how would we actually implement the brute force solution? Are we not gonna use recursion there? Will it be an iterative solution using stacks or queues?
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
8:47, I can;t understand what actually going on. On the node 3, length of node left node is not 0, it's 1. On the right -1, according to math. You firstly, say, that diameter of node 3 will be 1+ (-1) + 2 = 1, but it won't, you make direct cut, just changing left node length to 1? why?
Why we are not concern with Linked Node approch ... as compare to the array one? its easier that's we can say .. but is there any other reason why we don't land up for Linking Nodes and computing
Hi Neetcode! Is there any chance you redo this problem? There are a lot of feedback on this explanation not being the most intuitive, and there are better, more intuitive ways to solve this problem.
Although we can use a nonlocal.... Using a local would come handy to reuse the function... we cannot expect someone to declare a nonlocal for using this function
I rerecorded this solution since I thought it could be better, please check out this version instead: ruclips.net/video/K81C31ytOZE/видео.html
It's half the length and still covers everything.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Alternative mathematical approach: It made a little more sense to me to return 0 for a Null node. In doing so, you don't need the + 2 in the updating of the result. You are essentially accounting for the parent edge in different ways. I found this approach to come a little more naturally to me, so I'm posting in case it helps anyone!
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(root):
nonlocal diameter
if root is None:
return 0
left = dfs(root.left)
right = dfs(root.right)
diameter = max(left + right, diameter)
return max(left, right) + 1
diameter = 0
dfs(root)
return diameter
cannot agree more!
Thanks for this solution!
Thank you, now I see no advantage of using -1
What does the left + right part do exactly, and why is it needed? Im able to follow everything else though, just confused about that and why we are calculating 2 maxes.
@@bashaarshah2974 That's the diameter in current subtree.
In what universe is this an "easy" problem?
I was thinking the same thing during the video. If this is an easy problem then I'm a Porsche Cayenne.
@@HeinekenLasse Yeah this one is definitely a medium
I spend 1 whole day trying to solve this one but in the end had to watch this video
This is actually very easy if you don't do the -1 +2 bullshit.
All you gotta do is height of left, height of right and return the bigger of the two + 1 (to add current node) in each recursive call.
The diameter at each node is then leftHeight + rightHeight
Got confused during this video and solved it on my own first try in 5 min
Oh thank God someone else thinks so
If you are new to Data Structures and don’t understand recursion concept in Trees, don’t worry. I used to be like that until I find this channel sometime ago. White boarding is a must practice to understand Trees. Watch as many videos as possible. Later you can worry about the code. It will be that one snap of a moment you need to wait for to realize that you understood Trees. I had that snap of a moment. Don’t give up. We are Engineers 👩💻 👨💻
thanks man
Then we never use trees again after gettinga. job. Until we get layed off and have to do leetcode again
@@sarbjotsingh9998 explained my suituation here :p
thx bro
thx brodie
This one is quite difficult, do you think it should be labeled as medium?
should be mdeium, even be hard I think
@@maxchen7529can’t be hard，but I think it should be hard-medium
I think this problem deserves an update. The way you explained it is pretty complicated. It's way more intuitive to simply count the number of edges.
```
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root: return 0
diameter = 0
def dfs(node):
if not node: return 0
edges_l = dfs(node.left) if node.left else 0
edges_r = dfs(node.right) if node.right else 0
nonlocal diameter
diameter = max(diameter, edges_l + edges_r)
edges = 1 + max(edges_l, edges_r)
return edges
dfs(root)
return diameter
```
What's edges for though?
This looks amazing ! I came up with similar solution as Neetcode, but this looks more neat, Good Job!
I will credit you when I add this on leetcode.
Thanks.
My first solution was very close to this. Thanks!!
like this nonlocal thing in python does c++ too have this nonlocal stuff ?
@@siddharthd6141 In c++ you can simply pass the variable into an inner function as a reference
Great video! One question, why you use list type global res? why cannot you just use res=0 ? Thank you!
Python makes a copy of the primitive types if you pass them in the function so the value doesn't change outside of the function. He used a non-primitive type (list object) to make changes because a list object is stored on the heap and is pass-by-reference. He could've also made a class variable called self.res= 0 and used it in the function with self.res
@@ruspatel1996 Thank you so much for the clear explain! Really appreciate it!
@@ruspatel1996 Came here looking for just this question. Sort of a python 'gotcha' then.
@@ruspatel1996 isn't it more like this?
if we just use res we are assigning a local variable "res" inside a dfs function so when python interpreter meets "max(res,2+left+right" res doesn't have any value
but with res[0] it is not assigning it is actually reading value. so python interpreter will see there is no local variable "res" inside dfs function and move on to outer scope
@@dohyun0047yeah, i thought so too, at least in this case, you actually wouldn't need a mutable variable, a simple res=0 would suffice.
Edit: sorry, my mistake, it's a python scope thing, you do need a list, got it.
The arithmetic is unnecessary: if we return 0 in basecase and set diameter = left+right, the solution is still the same.
agreed. it's using depth vs using height which is the num of edges from root to bottommost node
thank you. The tricky part of this problem is the -1, +1, height, diameter. So many tutorials just take them for granted and offer no explanation, but you did an amazing job talking about the whys. Bags of thanks!
Yeah this was a breakthrough for me as nobody in leetcood discussions were talking about this and I was so confused.
I found this explanation quite difficult to follow, especially around 8:19, when NeetCode starts talking about "convention" to make the math work. The solution works, yes, but I am left a little dissatisfied with the overall explanation as it is still quite unclear. I don't seem to find this convention being used in other problems, but maybe that's because I haven't done enough of them yet.
think by yourself, nobody will think for you
@@user-ib3ev5pl2t Nobody is expecting the other to think for them, but if something is meant to make things easier, it should make things easier, otherwise what's the point? Clearly this explanation was off and made things difficult.
Agree with you. The maths should fit the problem, not the problem fit the maths
First of all, thanks for this fantastic channel! However, for this problem I find the following code way easier:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal max_d
if not root:
return 0
left_d = traversal(root.left)
right_d = traversal(root.right)
max_d = max(left_d + right_d, max_d)
return max(left_d, right_d) + 1
max_d = 0
traversal(root)
return max_d
This solution was easier for me to understand, thanks. What's the intuition around calculating max_d though? How do you know to use the sum of heights?
@@EE12345 the max diameter of a node is equal to the (max height of left + 1) plus (max height of right +1) - the longest path going through it.
however in this solution the +1 is already being incorporated in the return, so defining the height as "the number of edges being given to the parent node". which means that in this solution, height is 0 for null nodes and 1 for childless ones
I felt I could easily get so confused by this tricky -1 counting algo... later I found out another alternative which seems more clear to me is to just use max() to include both cases instead:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def longestPath(node):
if not node: return 0
left = longestPath(node.left)
right = longestPath(node.right)
nonlocal ans
ans = max(ans, left + right)
return max(left, right) + 1
longestPath(root)
return ans
Thank you for sharing this. I understood this method more clearly.
how this can be an easy problem
The core idea for this issue is pretty much the same as the Hard problem max path sum(lc 124),
for a node, we have two options,
1. split
2. no split
if we split at the current node, we'll have to calculate the path left -> current-> right.
In contrast, if we don't split we'll have to return the max path the current node could return to its parent.
Hope it helps
Very helpful!
Why is res initialized to [0]. I get that res = 0 gives a run time error. But how is res = [0] different?
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
why the global variable is set to res = [0] instead of res = 0?
that has to be a mistake. it does not have to be an array.
@@Incroachment
if you use res = 0 . changes inside the function won't affect the original variable outside the function,search for Immutable vs Mutable
res = [0] is no mistake, sure you can initialize it as res = 0 but then you have to use "nonlocal res" to make it accessible inside the helper dfs() function because integer objects are immutable objects ( if you try to modify it inside helper dfs() fucntion without using "nonlocal" the program will create a new object instead of using outer scope object). On the other hand list objects are mutable objects so can modify it anywhere in the program. #maile7853 #Incroachment
Out of so many videos, this is the first time that I think my solution is more clear and self-explained. :).
// Notice that when the tree is like a triangle, its maxDiamter is just left tree height plus right tree height.
var diameterOfBinaryTree = function (root) {
/**
* Returns the height of a tree.
* A tree with a single node is of height 1.
*/
function getHeight(cur) {
if (!cur) return 0; // The end of tree, height is 0
const leftHeight = getHeight(cur.left);
const rightHeight = getHeight(cur.right);
const curDiameter = leftHeight + rightHeight;
maxDiameter = Math.max(maxDiameter, curDiameter);
return 1 + Math.max(leftHeight, rightHeight);
}
let maxDiameter = 0;
getHeight(root);
return maxDiameter;
};
Why do you use [0] for res and not just simply 0?
you will get local variable referenced before assignment
unless you go self.res
idk why though anyone knows the reason?
@@richardyeh718 I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
Hi @NeetCode can you please explain why you take 'res' as a list not a variable.
that is becasue how python's scope works. you cannot modify the variable if it is in outer scope. u can still use a variable but u have to use "nonlocal" keyword before using res inside dfs to let python know that this is in outer scope
res=0
def dfs(root):
.......
.......
nonlocal res
res=max(res,2+left+right)
@@veliea5160 Thank you so much ...now it seems clear
@@veliea5160 thank you :)
thank you for asking this question
Also you usually use nonlocal if you want to make that variable global AND you want to modify it. If your not modifying and just looking then you can call it normally without nonlocal
I cracked at 'The leftsubtree is left right'
Why are we using res[0] instead of res?
It is in fact necessary to create a list here to store and update the final diameter value. The list in Python is mutable, meaning that you can update/mutate elements of a list whether the list is global or not. If you choose to use a global integer variable, then you always have to declare it is global inside your helper function to update it. Otherwise, you code will throw an error. Oh, and the global variables must be defined outside of the class. Code example below:
res = 0
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def helper():
global res
if not root: return -1
left = helper(root.left)
right = helper(root.right)
res = max(res, 2+left+right)
...
You may argue what if we pass res as a helper function's argument like "def helper(res):" and then can we avoid declaring that it is global? The answer is no. When you pass the variable as a function's argument, then it will only create a copy of the global variable that is in a different memory location from the global variable. This will result in keeping the global variable "res" unchanged the whole time. If you want to dig deeper on this, refer to this documentation. www.dataquest.io/blog/tutorial-functions-modify-lists-dictionaries-python/.
@@sf-spark129 Thanks for the doc link
@@sf-spark129 thanks for this! i was wondering the same thing
I think this solution will be a bit simpler to understand
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(root):
nonlocal res
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
res = max(res, left + right + 1)
return 1 + max(left, right)
res = 0
dfs(root)
return res - 1
Thanks for the vid but why are you initializing res to an array?
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
I made use of the maximumDepth problem to get the depths of the subtrees of a node, added them to get the diameter wrt a node. Then recursively called the diameter function on the left and right children and returned the max of the three. I felt this made sense to me from understanding standpoint. Putting my code for reference.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#find the depth of left and right subtree from each node. Sum them to get the diameter wrt that node.
#recursively call the same fn on the right and left child to get the same.
#return the maximum of the three i.e., current diameter, diameter of right child, diameter of left child.
def depth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
right = 1 + self.depth(root.right)
left = 1 + self.depth(root.left)
return max(right,left)
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
rightdepth = self.depth(root.right) if root.right else 0
leftdepth = self.depth(root.left) if root.left else 0
dia = rightdepth + leftdepth
return max(dia, self.diameterOfBinaryTree(root.right), self.diameterOfBinaryTree(root.left) )
Hope this helps!
For anyone reading this in future, this was my initial attempt too and did help me understand but it is actually O(N^2). Every call of depth will have O(N) complexity and diameterOfBinaryTree will also be called N times as we're calling it on every node.
the time complexity is the problem
This explanation and code is wayyyy better than the one on GFG... Thanks a lot!! ❤
Great solution💯. Thanks for the explanation. Something I noted about the solution. You set the global variable 'res' to be an array of length 1 instead of using an integer. This has been a problem for me in other recursive questions. Could you explain why an array works as a global variable in recursive questions and not integers? Thank you!
In python land, non-primitive datatypes such as list are passed by value. This makes it possible to update it rather making copy everytime. Hope this helps :)
@@niteshrawat576 Thank you. That makes sense!
can anyone explain why res is array instead of int?
same question, did you find the answer?
This is used as a workaround in Python. In Python, inner functions have access to variables in the outer function but they cannot modify them without using a workaround. Due to a quirk of Python's name binding, we can use a mutable object such as a list to bypass this problem. However, it is an awkward workaround and not the 'Pythonic' way to modify outer function variables. The proper convention here is to use nonlocal as shown below:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 0
def dfs(root):
nonlocal res
if not root:
return -1
left = dfs(root.left)
right = dfs(root.right)
res = max(res, 2 + left + right)
return 1 + max(left,right)
dfs(root)
return res
@@EverydayAwes0me ah yes, the "this technically isn't how the language is supposed to work but we're going to take advantage of its quirks" answer. Bad technique for the workforce.
Creating a list to store the update result is so inspiring.
Can you explain why you would use a list and not simply 0?
@@tonyiommisg List can update and store values by avoiding returning something in a helper function. In my habit, sometimes it is a little bit tricky for me to code with return in the helper function.
It's not just about avoiding your bad habit. It is in fact necessary to create a list here to store and update the final diameter value. The list in Python is mutable, meaning that you can update/mutate elements of a list whether the list is global or not. If you choose to use a global integer variable, then you always have to declare it is global inside your helper function to update it. Otherwise, you code will throw an error. Oh, and the global variables must be defined outside of the class. Code example below:
res = 0
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def helper():
global res
if not root: return -1
left = helper(root.left)
right = helper(root.right)
res = max(res, 2+left+right)
...
You may argue what if we pass res as a helper function's argument like "def helper(res):" and then can we avoid declaring that it is global? The answer is no. When you pass the variable as a function's argument, then it will only create a copy of the global variable that is in a different memory location from the global variable. This will result in keeping the global variable "res" unchanged the whole time. If you want to dig deeper on this, refer to this documentation. www.dataquest.io/blog/tutorial-functions-modify-lists-dictionaries-python/.
We can also use "nonlocal" inside the dfs() like:
res = 0
def dfs(root):
nonlocal res
...
@@mdazharuddin4684 nonlocal is a better solution
Is there a bug in this at: ruclips.net/video/bkxqA8Rfv04/видео.html ? You say D = L + R + 2, but you add it as D = 1 + -1 + 2 = 1, but shouldn't it be 2?
How does Diameter = L+ R+2? and why do you return -1 for a null node while in the "max depth of binary tree" problem we return 0?
The +2 accounts for 1 edge leading to each tree on the left and right.
res =[0]
I tried to change it to res =0, but failed because "reference before assignment", why a list can help solve the reference issue?
I tried the same thing. It is something to do with global variables, but I couldn't get it to work with just a standard int. Not sure why setting res to an array makes the difference.
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
res = 0
def dfs(root):
if not root:
return -1
left = dfs(root.left)
right = dfs(root.right)
nonlocal res
res = max(res, 2 + left + right)
return 1 + max(left, right)
dfs(root)
return 0 if res == 0 else res
@@singletmat5172 I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Hey i have a doubt regarding res variable I did very similar one with it, I used variable instead of array but I keepts throwing me local variable reference before assignment could you say what is wrong with it.
Use self.res instead of res for the variable.
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
What is the software he uses to draw? I definitely could help myself drawing some problems out
Excalidraw, or just paint lol
To avoid the -1 or 0 definition, one can build a graph based on the tree. Finding a path based on a graph is pretty intuitive. The process of building a graph based on a tree is mechanical. So, it is easy after some practice.
I didn't do it this way, my solution was based on your video on max path sum in binary tree. The principle still holds here.
Yeah this is true. It's way easier to remember also. Basically two problems for the price of remembering one!
var diameterOfBinaryTree = function(root) {
let max = 0
dfs(root)
return max
function dfs(root) {
if (root == null) {
return null
}
let left = dfs(root.left)
let right = dfs(root.right)
max = Math.max(max, left + right)
return 1 + Math.max(left, right)
}
};
inclusion of -1 for empty node makes it complicated:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res=0
def dfs(root):
nonlocal res
if not root:
return 0
left=dfs(root.left)
right=dfs(root.right)
res=max(res, left+right)
return 1+max(left,right)
dfs(root)
return res
The ambiguity of the problem comes from combining the two concepts together. The HEIGHT of the tree AND the longest PATH.
Those are not the same. Consider the binary tree:
1
/
2
The height of the tree is 2, but the longest path is 1 (the number of edges).
Here is a more explicit solution to the problem in Javascript (it should be pretty similar to the Python code). The variable "d" is not used really, but added to debug the state at the given moment.
function diameterOfBinaryTree(root) {
let max = 0
function dfs(root) {
if (!root) {
return [0, 0, 0]
}
const [,heightLeft, nPathLeft] = dfs(root.left)
const [,heightRight, nPathRight] = dfs(root.right)
// number of edges
const n = (root.left ? 1 : 0) + (root.right ? 1 : 0)
const d = n + nPathLeft + nPathRight
const h = 1 + Math.max(heightLeft, heightRight)
// the longest path
const p = h - 1
max = Math.max(max, d)
return [d, h, p]
}
dfs(root)
return max
}
8:44 you said D= 1+(-1)+2 = 1, that's incorrect. I think you just didn't cut it out properly because you corrected it right after.
Thank you Deve, I was thinking a lot about this in minute 8:44 , because I didn't understand :), it should be 0 + (-1) + 2 = 1
Same solution as others have pointed out, but with more understandable variable names so you can guess better what is going on:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def height(node) -> int:
if not node:
return 0
left_height = height(node.left)
right_height = height(node.right)
# Update the diameter if the current path is longer
self.diameter = max(self.diameter, left_height + right_height)
# Return the maximum height of the current node
return max(left_height, right_height) + 1
height(root)
return self.diameter
Hi,
I tried with another variable let's say t = 0 and used t at max function -----> this is not working showing as a variable is referred without assignment. But it is working with t= [0]. Could you explain why?
You have to use the nonlocal python keyword to do it that way. Otherwise it thinks you're using a variable local to the function, which hasn't been assigned yet.
@@NeetCode Got it!! Thanks a ton.
can someone explain why, res has to be a list?
what's the point of writing the result variable as a list? @12:45
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Mate keep explaining the solutions in shorts... It saves a lot of time
Also you don't have to do -2 operation if you use depth instead of height (I'm not sure if these are two same terms). Then depth of Null-node is 0, and depth of Node with no children is 1 (and so on). So in this way you have to only sum 2 depth. Code here:
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 0
def dfs(root: Optional[TreeNode]):
if root is None:
return 0
left_depth = dfs(root.left)
right_depth = dfs(root.right)
nonlocal res
res = max(res, left_depth + right_depth)
return 1 + max(left_depth, right_depth)
dfs(root)
return res
Banger.
Time complexity is O(N). what is the space complexity for this algorithm?
Worst case scenario, space complexity will be O(N) because of recursion stack
Imo -1 makes it more confusing, simply said, if there's 1 node in the left, then diameter to the left = 1, so diameter = height left + height right is more clear in this sense
-1 and 2+ is redundant complexety.
JS solution:
var diameterOfBinaryTree = function(root) {
let result = 0;
const recurciveSearch = function (node) {
if (!node) {
return 0;
}
const left = recurciveSearch(node.left);
const right = recurciveSearch(node.right);
result = Math.max(result, left + right);
return 1 + Math.max(left, right);
}
recurciveSearch(root);
return result;
};
@@TwoInaCanoe thanks
Не ожидал вас здесь увидеть)
I think returning -1 and making 2 + left + right makes it more complicated or at least for me.
The below is working perfectly fine as well.
def dfs(root: Optional[TreeNode]) -> int:
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
result[0] = max(result[0], left + right)
return 1 + max(left, right)
What app are you using to draw on screen?
first of all, thanks so much for your series and explanations.
@8:44 the 1 + -1 + 2 =1 can be ignored right? or am i tripping
why cannot we define a simple variable to store max but doing it as *res[0]* ? Not able to find answer in the web for this. I know i am missing something related to variables, lists and their behaviour with scopes.
yeah someone asked the same question below, apparently you can't modify a variable when you define it in the outer scope. You can modify elements of a list however, hence the usage of a single element list.
@@thndesmondsaid but his method of defining the list didn't work for me too. I had to declare the self.diameter first.
why use res[0] instead of res = 0
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
Why does he store the solution in the first index of an array? Could he just use a variable? has something to do with being visible inside the scope of the dfs()?
how come res = 0 doesn't work but res = [0] does? If I do res = 0 instead, I get a global constant error which I don't get.
Don't feel bad if you can't understand this solution, it's messy and unintuitive. There are much better solutions out there!
best explaination on recursive functions and binary tree diametre problem , thanks for the video , this video will blow up , ill share this masterpiece with my friends too :)))
U a God, another implementation without the -1 and 2:
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def helper(root):
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
self.ans = max(self.ans,left+right)
return 1 + max(left,right)
helper(root)
return self.ans
Him: "that makes sense, right"
Me: "oh shit, am a dumb ass" 😂
@NeetCode do you really recommend educative I have already done around 100 lc problems, will it help me?
Why res = [0] and not just res = 0. I tried it like that and got: UnboundLocalError: cannot access local variable 'dia' where it is not associated with a value
This is the best explanation that one could give on recursion. You are a great teacher 👍
Well explained, but I don't think it is intuitive to use the "-1" for an empty Node. Instead, we should do what we have always done for empty nodes; return 0.
This would make the code much simpler, as now you can get rid of the "2" and only write "res[0] = max( res[0], left + right )" (which makes more sense imho)
And as mention before, this is consistent with how we usually do DFS.
I think this small part of the code might have confused a lot of people as to why this problem is "Easy"
thanks for the effort into making the solution very carefully explained before jumping into the code
Even if we rewrite 2 + left + right and -1 for empty node AS just returning 0 for empty node and doing left + right. It works.
That is because in the latter, I am assuming that the height of the leaf node is 1 and not 0 AND height of empty node is 0, which alters the convention that height of leaf node is 0 and height of an empty node is -1. I don't know why they do it only that way when both ways could work I guess.
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = [0]
def dfs(root):
if not root: return 0
left = dfs(root.left)
right = dfs(root.right)
res[0] = max(res[0], left + right)
return 1 + max(left, right)
dfs(root)
return res[0]
My solution using recursion:
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def depth(node):
if not node:
return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
self.diameter = max(self.diameter, left_depth + right_depth)
return 1 + max(left_depth, right_depth)
depth(root)
return self.diameter
This was lowkey hard for an easy problem.
why does he use an array to store the result?
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Why if the diameter is not starting with root node we are bit adding 1 just adding height of left and right subtree whereas if it's root node we are adding 1 why?????
I just love how the LC introduction to binary trees is really helpful and understandable, then the following questions are like, "Now give me some space-age shit that requires three helper functions".
(Inb4 "ThReE LiTeRaL HeLpEr FuNcTiOnS" - it took one)
class Solution(object):
def __init__(self):
self.max_D = 0
def diameterOfBinaryTree(self, root):
self.dfs(root)
return self.max_D
def dfs(self, node):
if not node:
return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
self.max_D = max(self.max_D, left + right) # Update max diameter
return 1 + max(left, right) # Return the height of the current node
this is basically the max depth problem but you have to find the biggest left+right sum at a node.
Love your vids in general but this was just terribly explained. Absolutely awful. It felt like you didn’t even understand it fully and just copied a solution from leetcode. Why is result initiated to an array with value 0. Why not just 0
I somewhat understand the logic for needing height but you made no effort to even discuss its relevance. Why it’s important to distinguish from diameter for example.
Also why even set a null node to -1. Set it to 0 and set a non empty one to 1. If the node is non empty then just add 1
Is it really even important to have height ? After watching twice I have no idea
Horrid explanation and very disappointed given how nice some of your other videos are. It truly felt like you had no idea what u were talking about
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
what the hell is this problem, I still get lost why left is counted by left = dfs(node.left), I just don't know, there is no counting in the function at all. 😿
Because of recursion, at the end when you return 1+ max() you are effectively counting.
Hi can you explain why within the dfs function, we need to use "res[0]" instead of just "res"?
Because you cannot modify res inside of a nested function as its a nonlocal variable whereas lists are mutable. If you want to use res you can use nonlocal keyword to declare it inside nested function
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(root):
nonlocal res
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
res = max(res, left + right + 1)
return 1 + max(left, right)
res = 0
dfs(root)
return res - 1
@@YashGupta-ty2hn You are awesome!
Thanks Glad it helped you
Can someone explain why we are using a list here like res= [0] for storing the result, instead of self.res= 0?
python scope.
Python will look for the variable to mutate starting from the closest scope, and work its way up. The statement res = res + 1 (aka res += 1) it will evaluate from right to left (res + 1). Python will ask what scope is res defined in so I can access it; ah, I see within my scope I have a res =, so I will use that definition. Back to my res + 1, that res hasn't been defined yet (it's defined same line, which is obviously a syntax error), so I will throw.
The solution is to define res in the same scope, then within the inner scope tell the python interpreter it should look for the higher scoped definition with non local. So you can do:
bar = 1
def foo(x):
nonlocal bar
bar += 1
With neetcodes solution, you never "redefine" the variable, so it just works. Both solutions are unintuitive, but that's what you get with python :/
@@robpruzan7292 Thanks a lot for the detailed explanation 👍 .
Great explanation!!
why the res = [0] and not res = 0? we use it as an integer anyway? didn't quite catch that one
oh so it doesn't work with int type lol
Hi need code really amazing stuff, can i jsut check why is there a need to assign res =[0], instead of res=0
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
Solution.MAX_DIA=0
def dfs(root):
if root is None:
return 0
left=dfs(root.left)
right=dfs(root.right)
Solution.MAX_DIA= max(Solution.MAX_DIA,left+right) #diameter = left + right
return max(left, right)+1
dfs(root)
return Solution.MAX_DIA
I don't get how we use the height here and why we need it.
why the global variable was inside an array?
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Using a -1 for null nodes is really smart. If you don't do that, your code ends up in if statement hell. How do you come up with these elegant algorithms?
I would argue that this task is not Easy but Middle, because there are few gotchas and things one needs to realize.
Why does the res have to be res = [0], instead of res = 0 ?? I know that res = 0 doesnt work but dont understand why, can anybody help plz :) ?
I guess because of scoping? Python creates a new variable in the local scope, and will see the out of scope variable as immutable, so in order to use the global res you need the array to be a container? I guess... lol
Why we need to use res = [0] but not just res = 0? Thanks!
This has something to do with making res a global variable. Can someone explain why res=[0] makes it global? Also, if you wanna use res = 0, use the nonlocal keyword, works just as well.
So that we can change or update the values of list (which is declared at global scope) ...from function scope since...list are mutable and pass by reference.
how is this an easy problem on leetcode
why we return height in the bfs
Clear explanation with graphic. Thank you!
Solved without looking at NeetCode's solution, but came to check if there was some easier hack around the problem since it was labelled "EASY".
My solution was better than 92% in time complexity and better than 76% in space complexity.
class Solution {
public:
// return what value should get added to parent
// maximum possible diameter at any given is recorded in curr_max variable
int func(TreeNode* root, int &curr_max){
if(root == nullptr){
return 0;
}
else if(root->left == nullptr && root->right == nullptr){
return 0;
}
else if(root->left != nullptr && root->right == nullptr){
int left_path = 1 + func(root->left, curr_max);
if(left_path > curr_max){
curr_max = left_path;
}
return left_path;
}
else if(root->left == nullptr && root->right != nullptr){
int right_path = 1 + func(root->right, curr_max);
if(right_path > curr_max){
curr_max = right_path;
}
return right_path;
}
else{
int left_path = 1 + func(root->left, curr_max);
int right_path = 1 + func(root->right, curr_max);
int total_path = left_path + right_path;
if(total_path > curr_max){
curr_max = total_path;
}
return max(left_path, right_path);
}
}
int diameterOfBinaryTree(TreeNode* root) {
// there will be a current diameter for a path passing through current node
// you need to pass on the longer of the subtrees to the parent
int curr_max = 0;
func(root, curr_max);
return curr_max;
}
};
[3,1,null,null,2]
how is the result for this test case valid ????
Can someone please explain how would we actually implement the brute force solution? Are we not gonna use recursion there? Will it be an iterative solution using stacks or queues?
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = [0]
def height(root):
if not root:
return 0
left = height(root.left)
right = height(root.right)
return 1+max(left, right)
def diameter(root):
if not root:
return 0
left_height = height(root.left)
right_height = height(root.right)
diameter(root.left)
diameter(root.right)
res[0] = max(res[0], left_height+right_height)
diameter(root)
return res[0]
From a node...we need to find left and right depths.....and adding it.
We do the same from very other node.
@8:45 how is 1+-1+2 = 1 ?
Why is the height at root node of the left tree 2?
why have you set res=[0], can someone pls explain this?
I guess because of scoping? Python creates a new variable in the local scope, so in order to use the global res you need the array to be a container? I guess... lol
I didn't do the -1 but rather dealt with the null nodes programatically
8:47, I can;t understand what actually going on. On the node 3, length of node left node is not 0, it's 1. On the right -1, according to math. You firstly, say, that diameter of node 3 will be 1+ (-1) + 2 = 1, but it won't, you make direct cut, just changing left node length to 1? why?
Why we are not concern with Linked Node approch ... as compare to the array one? its easier that's we can say .. but is there any other reason why we don't land up for Linking Nodes and computing
Hi Neetcode! Is there any chance you redo this problem? There are a lot of feedback on this explanation not being the most intuitive, and there are better, more intuitive ways to solve this problem.
You should use nonlocal instead of res[0]
Although we can use a nonlocal....
Using a local would come handy to reuse the function... we cannot expect someone to declare a nonlocal for using this function
do related BT questions first eg. 110 Balanced Binary Tree and this will seem like an easy (as it should)