> give narrative/backstory on problem intuition ✅ > lowkey roasting his subscribers about going to the movies alone ✅ > literally holds tree during explanation ✅ > gives time complexity at end ✅ keep the videos coming, DAILY UPLOADS SOON™
you just explain the concepts so flawlessly I didn't have to go through your code just your explanation was good enough to write code myself. Thanks :)
I blindly give a like to your videos because I know it will always be awesome prior watching it 🙂. Thank you so much for wonderful channel Unlike others, you try to make it simple and best. I encourage others to also give a like because it is deserved!!
This explanation, especially the movie theater analogy really made me fully understand. Was watching a bunch of videos til I saw this one, thanks! Always a lifesaver!
This was such a great explanation. Better than the other top video where the guy just solves it and says "It's this way because... yeah... you need to recursively call the function... it's pretty easy if you don't know it then you should look up more"
Bit more clarification on Height Vs Depth of tree The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0. The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.
Thank you Python: class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 left = self.maxDepth(root.left) right = self.maxDepth(root.right) return max(left,right) + 1
Great Analogy with a clear explanation. Yes, Nothing wrong in going to Movies or to Restaurants alone :) Thank you for your videos. I subscribed to your channel :)
You can improve memory to >90% by getting rid of the two int variables and returning "return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); " Time is O(n), space also O(n) because we will have one call on the call stack for each node in case the tree is so unbalanced it becomes a list.
Hello Mr. Naughton, I am really looking forward to seeing the Tutorial on Dynamic Programming that you once mentioned it's coming. Thank you for your efforts making these videos. Kind Regards!
akanksha patel thanks Akanksha! If you like my explanations be sure to sign up for the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining the annual tier if you can!
you can visualize this, (you might have figured it out by now but for anyone else wondering) the left of node 3 is node 9 -> node 9 is a leaf which means the node 9.left == null ,node9.right == null both functions returns 0 because of the base case, so int left = 0 and int right = 0 (for maxDepth(9)) it then executes the next line which is to return the max of both of its left and right node and since they both returned 0 therefore Math.max(0, 0) + 1, which is 0 + 1 = 1 therefore the statement "return Math.max(left, right) + 1", returns 1 for the function maxDepth(9) if you follow the same approach on getting to the right of "node 3" which is "20", then maxDepth(20) returns 2 Then, the root which is the final function in the call stack, has executed both its left and right and they have gotten back to 20 with values of int left =1 and int right = 2 so, the statement "return Math.max(left, right) + 1" for the last function call, maxDepth(3), returns Math.max(1, 2) + 1 => 2 + 1 => 3 returns 3 (additional: the right row (node 20) told the node on the root that it is on level 2, which means the root is plus 1 of it from the leaves, therefore level 3) Hope this helps!
Hi. Thank you for explanation. How does a recursive method generate and int value? And how does an int value keeps adding up to give you a total of levels?
Thanks for the video, I totally understand the logic, but from the code perspective, would maxDepth(root.left) be called and do the recursion every time when mapDepth(root.right) is called? So for the maxDepth(root.left) is like double recursion?
Hi, is there any difference if the tree is balance? i know that the complexity is O(log n) in this case, but i don't understant how can it be if the code is identical? thanks!
If the input is a compact array representation of a tree, then the max depth of the tree is simply: return log2(array.length) + 1; Isn't it? If confirmed the array is not compact, then walk backward to find the first index of non-null value, and then: return log2(i) + 1;
Let's say you have a binary tree with only the left side and a height/max-depth of 3. 1 / 2 / 3 1: recursive call on 2 2: recursive call on 3 3: recursive call on null 3 returns 1+max(0,0) = 1 2 returns 1+ max(1,0) = 2 1 finally returns 1+ max(2,0) = 3 (height/max-depth of the tree) the return statement inside a recursively called function basically "passes the value up" to the function which called it
Guys, This might be simple question. But I am trying to visualize multilevel recursion with return statement. Please shed some light for my better understanding def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return max(left_depth,right_depth) + 1 I understood the basics of recursion but the return statement which is adding +1 is haunting me. i couldnt visualize
It keeps getting called recursively till the leaf node. At the leaf node it will return 0. This 0 gets carried forward and gets added by 1 for every level traversed in left and right subtree(only max of left and right goes forward). Hope it was clear 😅
I don't understand, Math.max(a,b) returns the maximum of two integers, I understand that once it has gotten to the furthest node in the tree it can propagate back to the root a number of times that will give you the number of nodes it's passed through, but I don't understand how Math.max(a,b) helps with that.
terrible. just copy pasted solution and no explanation on in-built parent,child,root properties of treenodes represented as arrays, really just terrible. may as well look at a solution and watch 10 minutes of some guy not helping you