> 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!
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.
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"
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
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!
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.
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
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?
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 :)
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!
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?
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;
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
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.
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!
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 😅
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
THERE IS NOTHING WRONG WITH GOING TO THE MOVIES ALONE
I have always wanted to try that and I completely agree with you :-)
@@saloneerege2006 Haha do it!!! This weekend that's your hw :)
I'd rather go alone instead of trying to catch the FlakyFriendException
@@jlecampana The worst kind of exception lol
you're just awesome mann!!! I like you're style and also remember...you make scene...always :)
> 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're my BOY Dom
@@KevinNaughtonJr nah , he is family
Dude, this theatre analogy has unraveled the concept of recursion in my mind. Best!
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 :)
This is the best description of recursion on the internet.
Thanks!!!
Never thought I would ever understand recursion, you just gave the best explanation. Thank you!
Anytime! Happy to hear it helped :)
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!!
Mohammed Nadeem thanks so much Mohammed I really appreciate your support!!!
The theater analogy is really good for explaining recursion. 👍
Mind blown at the theater analogy .. i dont think I will ever forget to do tree depth now... thank you
Your explanations are super clear and straight to the point. Thanks for helping me out!!
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!
LMAO I love the totally professional vibe and then there's just that random intro mumble rap
i literally thought i had another youtube video/spotify song playing the first few seconds lol
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.
Maulik Sakhida thanks for the extra info Maulik definitely good clarification!
nice explanation. This is the first time I am hearing you and I think the theater analogy is best explanation I have heard. (Subscribed you)
The Theater example was eye-opening. Thanks, Kevin!
It's important to mention that the +1 happens at each level, it is not only 'us' in the movie theater who're adding +1
Exactly!!! Thanks a ton for pointing out
that was the best explanation of recursion I've probably ever heard in my life lol
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"
beautiful explanation. I was really struggling with grasping the recursion conceptually but you're explanation was very helpful.
Thanks! If you enjoy my explanations i recommend joining a premium plan on the interviewing service I created! thedailybyte.dev/?ref=kevin
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
thanks for the python solution
Wow. I think I saw Stanford using the theatre example to explain recursion. They must've seen your video haha, great work!
hahah thanks Neal! Yeah there's a lot of ways to explain it but whatever makes sense :)
Best explanation of recursion I've ever seen!!
Thanks ! your movie theatre example will always come into my mind when I solve this ..
Sharmila Baskaran anytime happy to hear it was helpful!
Movie theatre analogy helped. Thanks for sharing
Anytime Shweta, happy to hear it was helpful :)
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!
Hopefully I'll have something and anytime I'm happy to help thank YOU for your support!
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.
The theater analogy! Damn Kevin.
great explanation!! Kindly make more videos explaining the concept of recursion in depth...because it seems a very troublesome topic.Thank You.
Best explanation of recursion EVER! It helped me so much to understand the code you wrote. ThanX, man.
I dont understand how left and right are incremented...
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
@@kozie928 Nice!
next time I am at the movies, I will ask the guy in-front of me, what row they are in
Awesome video! Your analogy made it so much more understandable.
Thanks Justin and I'm so happy to hear that!!!
you disturb the entire theatre
but nice anology
How is the count being calculated ? Since I don't see any incrementing going on.
At the end of each recursive call it is one being added.
Hope it helps
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!
Thanks for the movie theatre analogy . That make sense :)
Brilliant analogy
I loved the idea of movie theater was brilliant ! Very simple and intuitive. Thank you :)
Appreciate all the hard word you're putting in - really helpful! :-)
thanks Soumya!!! :)
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?
let's go to the movie theater to recurse.
I appreciate your analogies over Nick White's corny jokes (I still love Nick White's videos)
Wow, theatre analogy makes sense
happy to hear it!
As always GREAT info, to the point...keep it up!!
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 :)
Amazing analogy and Explanation .. Gonna recommend this channel to my colleagues and friends for sure ! Thanks :)
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!
The best explanation ever!!
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?
same thing here
love the analogy!
Great explanation!
GREAT Analogy!!! Thanks so much!
Thanks Mustafa and anytime!!!
Thanks, explanation was pretty neat.
fire analogy
best on youtube. actually
Awesome explanation Kevin!!
you are very good at explain things!
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;
Great explanation
Very nice example and explanation.you connected problem with real life
Thanks Raghvendra!!! :)
"in my case totally alone" hit me hard
Safari Star ahahah
@@KevinNaughtonJr wait what u true alone, but it got me a reply.
Thank you, following this I finally got it :D
Awesome Explanation ♥
Gold. Thank again.
is there a possible solution where we like keep a "count" variable and start counting from the root, instead of working our way from down up ?
So Math.max(left, right) + 1 compares the left and right subtree heights and returns which one is larger?
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
Intro music is 🔥
haha thanks Ian!!!
Genius !
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.
I don't get smething, where are we adding +1 for each levels?
I have the same question.
would appreciate if you could also explain the flow of the code with the example. Thanks
excellent example
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!
Seriously 😂 Google is asking u to find the height of the tree😂😂😂😂😂😂
Hi, should I memorize the tree node functions like maxDepth() for the coding interview?
Thank you.
great Analogy :)
Thanks Fnu :)
Why the depth is 3 and not 2? There are only 2 edges from leaf to root.
root.left or root.rigth , what do they return? I mean for example what is left in (int left= maxDepth(root.left)??
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 😅
what would root.left and root.right return?
Hey Kevin! Great explanation dude!! Just out of curiosity, have you tried solving this problem using BFS?
I haven't but I imagine it's just a standard BFS where you just increment the level you're on to find the depth
Also...test cases having exactly one node or two nodes are failing with this solution.Please Help.
Thanks ! :)
i got it at the end of the analogy
1:24 I understand 😐
King
hey i am rohit from india i have a query is this approch work as well as min depth ?
Great video bud :D
Thanks Shane!
Hey, is this solution more optimized than using BFS to get the answer?
Please, make a video on palindrome count of given string.
I’ll go to the movies with you bro lol
Could you provide solution for 849 problem?
Hello Sir, can you make a view on leetcode 289. Game of Life
?
Hey Nilanjan I'll see what I can do thanks for the suggestion!
Hey man can you do LRU Cache?
I'll see what I can do thanks for the suggestion Eddy!
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