Depth first search tutorial and problem solving (Binary Tree)

Today we are going to learn about depth-first search, DFS. It's a technique used to traverse the trees. So in DFS, we prioritize depth by traversing as far down the tree as possible in one direction until you reach a— until reaching a leaf node, so before considering other direction. So for example, we have a tree 1, 2, 3, 4, 5, 6, 7. In this The traversal will go from 1 to 2, 4, and then 5, then back to 2, then 1. Then it will go all the way to the right subtree, all the way to 6, then 7, 3, and back to 1. So we move exclusively with node.left until the left subtree has been fully explored. Then we explore the right subtree. The time complexity for this is O . V is the vertices and E are the edges connecting those vertices, and the space complexity typically is O. So if we have to look at the definition of binary tree, we can represent it as a class object which has a value and then left and the right object. So which is nullable of course, because if it is a leaf node then there will be no left or right object, but if there is one it will be assigned to this. And this is a common DFS traversal code template using recursion where we are passing a root to DFS and we are checking with the base case. If root is null, then return. Otherwise traverse to the root.left and root.right, and in that return the function. So till all the subtrees are traversed, visited through DFS, this function will run and then it will return the result. So there are 3 ways to perform DFS, which in general it does not matter how we are traversing DFS. But it is good to know how— what are the 3 ways to perform it. Sometimes it comes handy to write some logic when we are solving the problem. So 3 ways are preorder, inorder, and postorder. In preorder, logic is done before calling the children, which means that once the node is visited, the logic will be done and then we'll go ahead and call the children like this: dfs, dfs. So any logic will be done, will be done before this. In-order, this logic is done in the middle, that is after calling the first children. So in that case, in an inorder case, once dfs is called, then there will be a logic and then there will be dfs. So that is inorder, in between of both the children. And postorder is done after calling the children. So once dfs, dfs is done, then we'll do the logic. So the priority is visiting all the nodes and then doing the logic. So we have a code template for preorder traversal. So like I explained, so in preorder, the logic is done before calling the children nodes. So here we are just printing the current node value. So we are doing root.val and then we are calling the left and right child. So, so in this case, if you are passing this array as a tree, so what will be the result? It will first print the node value and then call the child. So in this case 1 is the first root node value, so that's why 1 is— it will print the 1. Then there is a second value which is— so this is the tree structure, so it will go to 2, then it will print the 2, then it will go to 4, print the 4, then 5, and so on so forth for right subtree. For inorder traversal, we first recursively call the left child then perform the logic. Okay, so like in the code template, we can see we have first called the left child, then perform the logic, and then we are calling the right child. So the printing will be in this sequence. First it will go to the— all the way to the left, which is 4, and then it will go to the parent node, then it will print that, then it will go to the right node, it will print that, then it will go back to the root node, print 1, and so on and so forth for right subtree. And similarly for post-order traversal, in this the logic will be done after calling all the children left and right. So no logic will be done until we reach a leaf node since calling all the children takes priority in post-order. So the printing will be done in this order. First it will print 4, which is the left subtree root node, left subtree left node, and then it will print 5, which is right node of left subtree. Then it will print 2, which is a parent of 4 and 5. Then it will go to the right subtree where it will print 6 and 7, which is left and right leaf node of right subtree. Then it will print 3, and then it will go to the root node. So that is how the post-order works. So bottom-up aggregation is one of the most fundamental design patterns for binary tree problems. So, and DFS is a perfect technique to use in such scenarios. So basically we are just building up the response from the bottom and returning back to the parent node. So because it is very difficult, or it is not very efficient, to determine the tree to determine its own height, size, or path without knowing the result from its subtree. So that's why by dividing to the base call and bubbling values back up the call stack solves the problem in O time instead of repeatedly calculating top-down with O complexity. So that's why this bubbling up plays a major role when we are solving tree-based problems. So DFS can also be implemented iteratively as well using a stack, but recursion makes it just easier to write code once you get to understand how recursion is working. So if you haven't learned about recursion, so first you need to understand how recursion works, and then we can— then you can easily understand how the DFS can be implemented to solve tree-based problem. So let's see, if we are given this array and we have to form a tree, then how we will form the tree? Okay, so we are saying, so when we have to print the tree, basically, so 2 is the starting node, which is a root node, and then we are saying, then we will print the left node, left child and the right child. And then it will come to the next line for the, for the left child values, but it is null, null, so we'll not enter anything. And then it is 12 and 5. So this is how we can print or make a tree from an array. So it is just easier for you to understand once you see the input in the question, and if you have to understand how these, these arrays are representing trees, it will just be helpful for you to visualize. And understand how these things are working. So this will be the tree structure for this array. Now let's look at couple of problems which are common problems for binary tree, and we can, we can start with the maximum depth of binary tree. So in this one we are saying find the maximum depth of binary tree given the root of a binary tree. Return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest, farthest leaf node. Okay, so basically if, and we have given, so let's take this example. We have 3, 9, 20. This array is given and that this is how the tree structure is forming. 3 is the root node, then left is 9, right is 20, then null, null— there is no child for node 9— and then 15 and 7 for node 20. And the maximum depth it is saying is 3. So maximum depth is 3 because This one, if you see, it is 2. Why it is 2? Because this root node also has value, right? 1. It is like 1 level. So for 9, it is 2. For 20 also, it is 2, but 20 has children, so the depth is more. So that's why it is 3. So this is 1, 2, and 3. And for 1, null, and 2. So basically it is root node is 1, left there is no left child, and the right node is 2. So the value is 2, 1 and 2. So if you have to solve this using DFS, so I think what we can do in this one is we can just— okay, so given based on the template which we saw here. Okay, so if you have to go with the template, so our base case is first is we are checking if the root is null. So let's just get done with root is null, then we'll just return 0. Okay, because when root is null, basically it's a leaf node, right? There is no value. It's not even a leaf node. There is no value here, so it will return 0, right? And then we are saying we— and then DFS also, what, what is the template? The template is saying call recursion recursive method for left and right. So that's how we are going to visit it. So if we are calling this, so we can just call on the left. And same way we can do for right, right? Okay, so now once we have this, we are going to return the max in between of both. So how we can take the max? We can take the max of left or right. So whichever, because it is a bubbling up event, so the values which are— so once the call stack starts popping up, it will return the value and then we can compare. And each return, each call stack will have its own scope of variables. That's why these values will be— will not corrupt each other. So that's why it can compare. For the left and right subtree, which value will go bubbling up. Okay, but in this one we also have to pass current node value. So with this, let's run this and see that if the test results pass. Yeah, so we can see the test result passed. So yeah, using the same template which I have here, we can easily put that and solve a problem. And see how that is, how with minor changes we are able to solve this. Okay, now let's take a look at count good nodes in binary tree. So this is a medium-level question. It says count good nodes in binary tree. Given a binary tree root, a node x in the tree is named good. If in the path from root to x there are no nodes with a value greater than x, return the number of good nodes in the binary tree. So basically what question is asking is, so if you are traversing the tree and there are no values greater than the current node value till from the, from top to till this level, then it's a good node, otherwise it's not a good node. So basically it is increasing order, so the values are going in increasing order, increasing or equal. Okay, so that's what it is saying, right? That's why if you see here, when 1 is not a good node because 3 is greater than 1, but 3 is a good node because 3 is equal to 3, it's not less than 3. Same for here. 4 is a good node because it is greater than the previous. 5 is a good node because it is greater than previous. Okay, so basically it is saying like we have to— same thing in this also. We are trying to doing the traversal and then we are trying to check whether this current node value is greater than the value— any previous values, right? Greater or equal than previously. So basically we are traversing and keeping a track of it. So, and in this one we are doing a logic preorder traversal, which is this one, okay? Preorder traversal. So basically before we are calling left and right, we are going to check whether the node is good or not. Okay, so let's try to solve this. So it is asking us then return the number of good nodes in the binary tree. So let's just take total good nodes variable, and this is what we are going to return in the end. Okay. And then we are doing— I'm just naming it preorder DFS. That does not change anything, but it is just for the clarity that we are solving this using preorder technique. And then we are saying we are passing a value here, and then we are also passing one more value because like I mentioned we are trying to track the value for comparison, and then we want to compare against the current node value. So we want to track what is the maximum value so far in the traversal. And same thing, first is the base case as per the recursion rule. If node is null, then we are going to just simply return. Okay, and like I said, it is a preorder. So before calling the— before calling children, we have to do the logic. So do logic here, but let's complete the calling and then we'll revisit the logic. .left And same thing, node.write. Okay, so this is what we are doing here. Then what is the logic? First thing we want to do is we want to check if node.val is greater than or equal to max so far. If it is, then we'll just append the increment the total good nodes, right? That is what we want to track, and that is what we are returning. So if it is this, then we are incrementing total good nodes. If— and there is no else condition for this. And then we want to also update our max so far because we have to keep track of the maximum value. So we'll just say maxSoFar and node.value. Okay, so this is the business logic we are doing. So what will happen— I'll just delete this now. So now what will happen is it will come here, check if the node value is greater than or equal to maxSoFar. If it is, it will just increment the variable And then next it will update our maxsofar. In case current node value is greater than max value, it will update the value and then we'll call the left and right node. Now we'll have to call this function first. So we are calling with root and then we also have to pass maxsofar value. So we are calling root. So let's just pass root.value. Okay, let's run it. Oh, here also we have to pass the value so that— so for all the recursive calls, we are passing the max value so far. Okay, this is a medium-level question. Okay, so next is maximum difference between node and ancestor. So let's take a look at this one. So given the root of binary tree, find the maximum value v for which there exists different nodes A and B where v equals to difference of node value, A node value and B node value, and A is ancestor of B. A node A is an ancestor of B if either any child of A is equal to B or any child of A is ancestor of B. So yeah, this question is just the language is little bit I think confusing, but let's take a look at the example. So again, we have this tree. So we have various ancestor node difference, some of which are given below. So 8 minus 3 is 5, 3 minus 7 is 4, 8 minus 1 is 7, 10 minus 13 is 3. Among all possible differences, the maximum value 4 is obtained. So I think basically we are just trying to Track the min and max value and get the difference till we know, and return get the difference and till we know what is the maximum difference. And that is what is the answer, right? Same is with this: one null two null zero three. So does zero minus three is the maximum difference? So And we are returning absolute value. So 0 3, 3 is the answer. So I think approach is here, like I said, approach is basically you're just keeping track of min and max, and then we are returning that. So looking at this, seems like we can solve this also using preorder. Where we'll first do the logic, then call the children. And it is a bubble up, it is going to bubble up because in the end we are going to return the maximum difference, I think, right? A node is ancestor and we have to return the maximum difference. Okay, so if you have to solve this, so again let me create one function which is going to do a DFS responsibility. And because it is going to return and we are not storing in this one value in external object, This function is going to compute everything and in the end it is going to return. So I'll just make it a return type function. Okay, and then let's see, first same thing, if node return. Okay, so in this one, because we are bubbling up, then once we reach to a leaf node— so that is a base case, right? Once we reach to a leaf node, when node is null In that case, we want to do some logic here. Okay. And we need to track the maximum and minimum value of the path. So let's put those current min in the param— in the function parameters so that we can keep track with every call. And then we can just return Math.absolute, which is this one, right? Current value, current max, and current min value. Basically, we are— that is what we are in the end trying to calculate, right? So current max minus current min. Okay, we don't even need Math.abs because we already know what is max and min. Okay, and then in this one, we are going to say we have to calculate current max, which is a Math.max of current node value or current max value, right? Like we saw in the previous example also, how we were— and current min is current min node or node value. Okay, so now this is what we are going to pass, and this is how we are going to calculate the value. But the question is, uh, How we are keeping, how we are returning in the end, right? So same thing, we are going to do the bubble up event. We will call preorder TFS and we are going to call node.left and we are passing current min, current max. Hence Same with this, pre-order TFS node.right, current_min, current_max. So these are going to call all the nodes and in the end we are going to return math.max of left, right. Now how it is going to return the left or right because we are calculating— once we hit the base case, we are calculating the difference and that's what we are returning. So that's what is going to be in the left or right, and in the end we are returning that. So now let's call this function and We are passing root and starting position. We don't know what is the min and max, so we'll just pass the root.value. And as the event goes on, it will change, track the value, update the value, and pass it on. Okay, yeah, so see, using the same template with minor adjustments, we can solve medium-level questions. Just the mental model we have to make sure that we are following based on the template. Now let's take a look at another example, diameter of binary tree. Okay, diameter of binary tree is Basically, root of a binary tree is given and we have to return the length of dynamic— of the length of the diameter of the tree. So diameter of a binary tree is the length of the longest path between 2 nodes in a tree. This path may or may not pass through the root. The length of path between 2 nodes is represented by the number of edges between them. Okay, so I think this line may or may not pass through the root is little bit confusing because if we take a look at the binary tree structure, root will always be there for the longest path. So if you keep expanding or keep increasing this tree, okay, it will still— if it still goes, it will traverse all the way here till here. You know, you're getting my point, right? So it won't be like it will go 2, 5, 5, 2, 4, right? Of course this can be there, but, uh, or if it is, there is one more node here, it can be like this. So that's why it is saying may or may not. But root, we can safely assume that root will always be part of the longest path between the tree. So if you take a look at this example, so 4, 2, 1, 3, 5, 2, 1, 3 is a valid example. So how we'll solve it? Because we have to solve the diameter of, diameter of binary tree, and we need to know that, we need to know the longest path between 2 nodes in a tree. So it means we can do a postorder. So the priority will be to visit first all the nodes and then calculate the answer and return it. Okay, so because it is— it says get the diameter, so let's just take a variable to track it, and this is what we are going to return. And because we are first visiting all nodes, so let's just call it postorder DFS. Okay, we are not returning anything back from this one, so we can just do it void or keep it Like this. Okay, and then same thing, go with the template. If node is null, then we are returning 0 or returning nothing, whatever. Okay, so because it is a postorder, so first we'll call the children.left, but we need to also do a bubble up. So bottom-up aggregation is basically— we are, like I mentioned before, we are sending value from bottom to up. So to capture the value, we'll just take into the variable And then once we have the value, now once we called all the children, now we have to do a business logic. First business logic is to get the diameter. What is the formula for diameter given here is the longest path between 2 nodes. Longest means max, right? So max Of what? Of diameter, because it's just a path and we want to track the path. And then the— we are passing the— and, uh, we are passing the— and the second value is we are passing the value of 3 paths. So from left to right, so we are saying what is left plus right is our diameter value. So this is our diameter value. And then in the end, once we are returning here, we are saying Math.max, same thing, same logic. We are bubbling up the event, so we are returning max of left or right, left or right, and we are adding 1 to it. So once the call comes, it will go all the way to the 4, and 4 will return 1 back Then 2 will return 2, then 3. 1 will have its own value of— because it's one level— 3. And then 3 will return 1. So 3 1, 4 will become. So 3 will become the answer. Okay, so this will become— so We have to call the, yeah, order DFS, and we are calling the value root. And let's run it. So these are the 4 problems we have solved using DFS preorder/postorder code template. So follow this code template and it will just make easy to solve the problems using this approach and with minor business related to problem, adjusting some business logic, we'll be able to solve the problem.