Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python
ฝัง
- เผยแพร่เมื่อ 15 ก.ค. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/depth-of...
0:00 - Read the problem
1:28 - Recursive DFS
5:30 - BFS Solution
10:43 - Iterative DFS
leetcode 104
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - วิทยาศาสตร์และเทคโนโลยี
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
this was really good, thanks foe showing us the different ways to solve the same problem because its like learning more than one thing at the same time (BFS, DFS, recursion, binary tree traversal, queues, stacks, etc. all in one video)
Your explanations have always been pretty amazing, but somehow they keep getting better and better!!
Thanks, I appreciate your kind words more than you think! 😃
The third solution should replace the order of "left" and "right" of the stack.append to become a pre-order tree traversal.
Hi Neetcode, Great work, keep it up!
In iterative dfs, I think you should append the right node first because then it should be preorder traversal. But both will work the same anyway.
Thank you so much for the diagrams sketch! It became clear now
Thank you NeetCode for this series!
I've watched his videos for a while. This is one of the best lectures. Thank you so much.
Such a clear explanation! Thank you :)
God bless you. I have stumbled on your channel and it has been helping me a lot with your explanations. I like how you did all three ways of doing this to help build that intuition for all of them. Thank you so much for making these videos.
thnx for showing the different approaches
I had only coded up the recursive way, but good to know about the other 2 ways you described in this video
This is an extremely wonderful explanation. Keep up the hard work. Btw, it is the post-order method for drawing the third solution. The code of the third solution is a pre-order method. Anyway, It doesn't matter the result of this question. We can take either of pre-order method or the post-order method.
love you bro for great logical solutions
Thank you for the clear explanation! You are wonderful :)
I loved this. Thanks sooo much.
Thanks for the explanation.
Excellent explanation!
Wooow... almost one line solution ))) You are amazing!!!
Thank you very much for your videos!
Great video as always
At first it is confusing for me but then I realized and your ideas are really effective
Your videos are really very informative and helps a lot while solving questions .💙💙
Hey, Can you tell me why are the leaf nodes returning 1 ? I think they should return 0 because their height is 0, so the height should be 2 right?
Hello, thank you so much for your amazing content, I am devouring your insights and its helping me grow while gaining confidence. My question, for DFS and BFS, should it be ROOT in the answers opposed to NODE? Thank you.
5:11 made me laugh @neetcode...."I am showing that I am not able to solve even easy problem"
Somehow, I feel like the iterative dfs is not so `dfs`, it's till kind of `bfs`.
What makes it DFS is that new nodes to search are appended on the right, which is the same place where nodes are popped from. This means that deeper nodes of depth X + 1, which were found from a previous node at depth X, will always be tried before potential other nodes of depth X.
great, this is helpful.
Thank you so much.
Awesome explanation ❤️
Can you plz make a video on N Queens problem?
IDK if this changes anything and if it doesn't can someone explain why. In the last solution when you added things to the stack you appended node.left and then node.right but for preorder traversal shouldn't have node.right been appended then node.left so when you pop the stack the left node is popped first ?
Excellent diverse approaches! The code explanation of the last one was pretty confusing though.
Hey, Can you tell me why are the leaf nodes returning 1 ? I think they should return 0 because their height is 0, so the height of the tree should be 2 right?
because the no. of edges will be the height right?
for BFS, couldnt we just use your iterative DFS solution, but replace the stack with a queue?
good work sir
thanks! right should have been appended before the left yes ?
Simply awesome
Hey NeetCode,
In the Iterative DFS approach, within the while loop, if we append like this
stack.append(node.left, depth+1);
stack.append(node.right, depth+1);
When we pop in the next iteration, then the right child will be popped and their children will be added right (because the right child is added last in the stack). I think the order should be reversed here so that the left children will be popped in the next iteration
The results will be the same in either way.
for the DFS iterative, why do we need to add the Null Node to the stack? We can do :
if node.left:
stack.append([node.left, depth+1])
if node.right:
stack.append([node.right, depth+1])
We can also choose to not do that and still the result will be the same.
additional if-checks as part of the code, that is all!
Hey as we are following pre order , the order shd be root, left, right then as stack follow lifo shdnt we insert right first and left, this is small doubt anyway technically we will get same. sorry for asking a lame doubt please excuse me.
BFS is useful for Leetcode 111.Minimum Depth of Binary Tree. Once you find the first leaf node, (not cur.left and not cur.right) return 1 + depth
you might be the best at explaining these types of problems, and the theory behind them, wow
Thanks!
Thank you for the awesome explanation. Where can I find the excel sheet at the beginning of your video? I liked the short solution hint
@neetcode - heads up, the link to this video on your website actually takes you to the comments page instead of the video itself.
thankyou bro for adding the C++ codes on your website i do use fully your website .....and love you so much from India
No problem, glad it's helpful!
Can you explain why we used 'self', even when we were in the same function (a reference to recursive solution line#12)
It's required in python, since the function belongs to the object (self)
How do you create these videos like on iPad or on the computer as its difficult to drawing otherwise ?
@ 11:25 you said in pre order traversal, we visit left tree first. That's not pre order, In preorder we visit the root node first, then the left and right trees.
Thank you Sir for your work, hardly appreciate that. I actually have a question about the 2nd implementation. If we user pop instead of popleft or use stack as list of values we have an issue for asymmetric trees. In this case we always have +1 vaules of levels. I have checked it with debugger and I don't understand yet why in case we append to the list it add instead of list to the upper Tree element a new one..
I’m a bit confused on the DSF on why it would be max(result, depth) wouldn’t depth be good enough?
On the Iterative DFS explanation if its using preorder wouldn't 9 on the left subtree be added first to the stack and then 20? It looks like 20 was added first and then 9.
I have the same question
I usually don't like recursion, but it was the simplest one. xD
0:36 😂 You are very funny brother
range(len(q)) bothered me a lot until I looked up that it was only evaluated at the start of the for loop.
Do we really need the for loop inside the iterative bfs algorithm? Esp when this is a binary tree?
The explanation is very good. Please let me know where I can get this code. Please share the link
Do I even have to say anything, good video!
Looking at the recursive dfs solution, how does traversing through each node return the value of 1 just by calling the function? so for example in the return line at 5:10, how does self.maxDepth(node.left) generate a value to be compared with in the max function? I don't see how it gets incremented with every function call?
Just like to add the explanation of the algorithm is great, its just from a coding standpoint I don't understand because self.maxDepth(node.left) by itself returns 0
I am also confused about this, if anyone can provide a clear explanation of how a node generates a return value when recursing that would be very helpful
That's because we're adding 1 for each level. So for example, in the recursion, if the tree is empty, we return 0. That would terminate our code and return 0. But if our tree has at least a root, then the depth becomes 1. so we add that value for each level we encounter. that's why the recursive code is return 1 + max(maxDepth(root.left), maxDepth(root.right). So this means, as we go deeper into the tree, we keep adding 1 for each root or level. But once we reach the leaf nodes, the root.left and root.right of the leaf node would return 0.
For example, if we have a tree with 3 levels,
a
b c
d e
our function call would be 1 + max(maxDepth(b), maxDepth(c)).
maxDepth(b) would be 1 + maxDepth(d)
maxDepth of d would be 1 + max(maxDepth(d.left, d.right))
both d.left and d.right are none (we hit our base case). Therefore they both return 0.
This means maxDepth(d) would be 1 + 0
maxDepth(b) == 1 + maxDepth(d) which is 1 + 1
maxDepth(a) would be 1 + maxDepth(b) which is 1 + 1 + 1
So the function will finally return 3.
Btw since the tree is symmetrical, I only took the a->b->d part of the tree for this explanation.
10:53 Isn't the recurisve DFS a post-order traversal? We first do left, then right and then the current node right? Atleast that's how your code looked in the first solution
5:07 I died
Do you think if I solved this question in a real interview with just recursive DFS would that be enough or should I also learn the iterative way to solve it too just in case.
Know iterative and recursive solution
@@legatusmaximus6275 Thanks
The BFS and DFS are both iterative right
For this particular problem using DFS, why did we opt to use the max keyword? I don't understand the reasoning behind this.
It is always better to actually write down the recursive calls' results step by step. Then, you will see why you need max() in the return statement. It took me about 10 problems of Binary Tree until I see that naturally.
To answer your question, DFS goes deeper and deeper(lower and lower) of the tree recursively until it reaches a leaf node(base case: root = None). From there, it starts building up like climbing up a tree. Let's say you have climbed a good amount on the left side of the tree and also a good amount on the right side. You really can't tell which side you climbed more. Then, max(left, right) will give you the higher side's height(depth) instantly. When you go one step higher, which (let's assume) is the root, then you will get the maximum height(depth) of the tree by 1 + max(left, right).
Code I use to understand below:
def maxDepth_DFS(self, root: Optional[TreeNode]) -> int:
if not root: return 0
leftNode = self.maxDepth(root.left)
rightNode = self.maxDepth(root.right)
return max(leftNode, rightNode) + 1
Is there an equivalent Java version of implementing Max Depth of a tree using DFS/stack?
public int maxDepth(TreeNode root) {
Stack stack = new Stack();
stack.add(new Pair(root, 1));
int depth = 0;
while(!stack.isEmpty()){
Pair temp = stack.pop();
if(temp.treeNode != null){
depth = Math.max(temp.integer,depth);
stack.add(new Pair(temp.treeNode.left, temp.integer + 1));
stack.add(new Pair(temp.treeNode.right, temp.integer + 1));
}
}
return depth;
}
public class Pair{
TreeNode treeNode;
int integer;
public Pair(TreeNode treeNode, int integer){
this.treeNode = treeNode;
this.integer = integer;
}
}
Why is the last solution DFS Preorder? Shouldn't it be considered as Level Order (BFS)? It goes through nodes by each level (visit/process siblings first) before visiting its child.
I understand people normally say Queue is BFS and Stack is DFS, but I don't understand this concept. They both look BFS to me whether they use queue or stack, because you visit the nodes from top to bottom, visit/process siblings first before visiting/processing its own child.
It's a question I had for some time, hope someone can answer 😛
I am thinking the same! Thank you for asking it and hope to see the answer from the author too!
That is only because the example tree doesn’t have much of a left side so the traversal gives the illusion of being BFS. However, say node 9 had children 4 and 8. Then we’d visit both 4 and 8 before 20 instead of going right from node 9 to 20. So it’s really just a crappy tree to use as an example bc it doesn’t differentiate BFS and DFS
understood
Can anyone please explain the syntax? I'm very new to OOP with Python, and I don't understand how we actually get the entire list of nodes (for instance "Input: root = [3,9,20,null,null,15,7]") through the treeNode class object which is not even a list...".
Its misleading, root is actually just 3 in that example, they shouldn't call the list root, the list is the entire tree, but only the root (3, with it's left and right (9,20) filled ) will be passed into the maxDepth function
In a binary tree, the node value on the right should always be greater than the node values on its left, and also the parent node. Does this make the example given by leetcode wrong?
hate to sound stupid but confused on this one. ive been understanding recursion pretty well but this problem says the input is a root node, but it looks like the input isn't just one node but multiple items in an array. so is the whole array being input as root or just the first one. if its the whole array. would if not root always be true and always return 0. please hellp
The input is the root node but the root node is an object of the class Tree node (the class is defined in comments in the video above the solution class ) which has 3 properties the value, the left node and the right node. You can access all the nodes of the tree just from the root node.
I hope I was able to help
Another variant is:
def solution(root):
cache = {}
return helper(root, cache, 1)
def helper(root, cache, level):
if not root:
return True
cache[level] = root.val # [root.val]
helper(root.left, cache, level+1)
helper(root.right, cache, level+1)
return max(cache.keys())
I'm wondering how to transform list to a tree object?
Is there a python code to do that?
check out this problem -> leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
you are smart
♥
could anyone explain why res = [0] instead of res = 0?
isn't the maximum depth same as the height of the tree?
A stack in python can hold 2 elements?
I believe the stack in Python is simply a list, and a list can hold individual elements, as well as tuples that hold two elements. This stack just holds a tuple of [node, depth] per node!
I lost it at 00:35
For some reason your BFS solition won’t pass this case on Leetcode today. [3,9,20,null,null,15,7]
The solution has a mistake, level should start from zero
final bit of code doesn't match up to drawing as it actually pops the right node first? correct me if wrong
you are correct. both work, but swap the order of how its pushed to stack to get pre order (NLR)
This is technically an alternative pre order of NRL
Hi @NeetCode i am unable to grab the recursive and backtracking concept clearly.I have gone through all the videos but still unable to think about a solution using recusrsion and backtrack. will be of great help if u can guide me on the same
He is not alive
@@naveenprasanthsa3749 Yes he is lol
Iterative Depfasajsdkdnf lol😂😂🙏🏻
For the BSF approach, you don't need base case if you code like this:
Instead of using "if not root: return 0",
q = deque([root]) if root else None
will do just fine.
This is more NeetCode-ish style of code I figured. Yes, you like to keep your code succinct although that can be sometimes difficult to follow. :)
Code below:
def maxDepth_BFS(self, root) -> int:
q = deque([root]) if root else None
level = 0
while q:
for i in q:
node = q.pop()
if node.left:
q.appendleft(node.left)
if node.right:
q.appendleft(node.right)
level += 1
return level
lol. Breadth first search and depth first search are literally tongue twisters. Better say bfs and dfs.
what do you mean? It's just depfarstsaerch and breithfasbtshsearsch.
don't forget 'f' in between like me...😂 imagine saying BS in the intervew
I am not good with Recursion and tree thats why I cant even solve the simplest one liner solution...............
create
in python we don't use camel case. it's snake case.
for i range(len(q)). oh my
buy thanks for the content
I have a crush on you Neet..
How stack bottom becomes stack top in 3rd approach. pls explain
Generally stack should start from bottom, but while explaining he started putting items at the top (like a table) which is actually the bottom of the stack.
I did catch the node --> root. But ... here's what my aMaZiNg code resulted in -
AttributeError: 'Solution' object has no attribute 'maxDeapth'. Did you mean: 'maxDepth'?
**cries in the corner**
fyi, depth does NOT include the root (height of a tree does), the LeetCode description is wrong, root node is always at max depth 0.
Thanks!
Thank you so much Ajay!!