> 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 :)
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!
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 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.
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!
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 :)
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
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!
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
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
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!
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.
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
![อยู่คนเดียวกับเขา - ส้ม มารี (Zom Marie) [Official MV]](http://i.ytimg.com/vi/gq1cWAIQDLg/mqdefault.jpg)
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 :)
Never thought I would ever understand recursion, you just gave the best explanation. Thank you!
Anytime! Happy to hear it helped :)
This is the best description of recursion on the internet.
Thanks!!!
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!
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
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)
that was the best explanation of recursion I've probably ever heard in my life lol
Best explanation of recursion EVER! It helped me so much to understand the code you wrote. ThanX, man.
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
Your explanations are super clear and straight to the point. Thanks for helping me out!!
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"
Best explanation of recursion I've ever seen!!
The Theater example was eye-opening. Thanks, Kevin!
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!
The theater analogy! Damn 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
Awesome video! Your analogy made it so much more understandable.
Thanks Justin and I'm so happy to hear that!!!
Thanks ! your movie theatre example will always come into my mind when I solve this ..
Sharmila Baskaran anytime happy to hear it was helpful!
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!!! :)
next time I am at the movies, I will ask the guy in-front of me, what row they are in
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 :)
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!
Hopefully I'll have something and anytime I'm happy to help thank YOU for your support!
Movie theatre analogy helped. Thanks for sharing
Anytime Shweta, happy to hear it was helpful :)
great explanation!! Kindly make more videos explaining the concept of recursion in depth...because it seems a very troublesome topic.Thank You.
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!
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?
I appreciate your analogies over Nick White's corny jokes (I still love Nick White's videos)
The best explanation ever!!
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 :)
Thanks for the movie theatre analogy . That make sense :)
As always GREAT info, to the point...keep it up!!
you disturb the entire theatre
but nice anology
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
Brilliant analogy
Thanks, explanation was pretty neat.
Awesome Explanation ♥
Thank you, following this I finally got it :D
let's go to the movie theater to recurse.
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!
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!
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
Great explanation
GREAT Analogy!!! Thanks so much!
Thanks Mustafa and anytime!!!
Wow, theatre analogy makes sense
happy to hear it!
Awesome explanation Kevin!!
Great explanation!
love the analogy!
you are very good at explain things!
best on youtube. actually
fire analogy
Very nice example and explanation.you connected problem with real life
Thanks Raghvendra!!! :)
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 ?
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;
Gold. Thank again.
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
would appreciate if you could also explain the flow of the code with the example. Thanks
Thank you.
Genius !
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!
"in my case totally alone" hit me hard
Safari Star ahahah
@@KevinNaughtonJr wait what u true alone, but it got me a reply.
Why the depth is 3 and not 2? There are only 2 edges from leaf to root.
I don't get smething, where are we adding +1 for each levels?
I have the same question.
Hi, should I memorize the tree node functions like maxDepth() for the coding interview?
excellent example
Intro music is 🔥
haha thanks Ian!!!
what would root.left and root.right return?
Thanks ! :)
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.
Hey, is this solution more optimized than using BFS to get the answer?
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 😅
Also...test cases having exactly one node or two nodes are failing with this solution.Please Help.
hey i am rohit from india i have a query is this approch work as well as min depth ?
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
great Analogy :)
Thanks Fnu :)
King
Great video bud :D
Thanks Shane!
Seriously 😂 Google is asking u to find the height of the tree😂😂😂😂😂😂
Please, make a video on palindrome count of given string.
Could you provide solution for 849 problem?
I’ll go to the movies with you bro lol
i got it at the end of the analogy
1:24 I understand 😐
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