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)
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.
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.
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.
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.
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 ?
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
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])
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?
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.
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.
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
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.
@ 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.
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.
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.
Can someone recommend me some visaulization platforms to see how the code and logic works together? For example, the recursive calls. I am not 100% with recursion so wanted to see it
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
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 😛
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
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
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?
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
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
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**
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
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 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!
