Breadth first search (BFS) tutorial, understanding common pattern and code template.

Okay, today we are going to cover breadth-first search, BFS pattern, which is used for traversing the nodes in the trees or the graph. We'll look at how we can implement BFS, what type of problems you can solve using BFS, and some code variation. Try to calculate code complexity, and then I'll share 2 code templates with you which is commonly used for BFS, and then we can also look at couple of LeetCode problems and try to solve it. Let's start with it. So the structure which you are seeing here is a tree structure, tree data structure. So if we want to traverse a tree from top down, level to level, then BFS is our default choice. Another approach is DFS, which is depth-first search which traverses all the way to the down and then goes to the next node. But in BFS, it usually goes, it always goes from first level to second level, then it will visit all the nodes, then it will go to the next level. So which is a very useful technique to solve many different type of problems where we want to traverse level by level. For example, if we have to find the shortest path from one node to another node, BFS is a good choice. If we want to find the sum of the deepest levels or find the min-max values in the level nodes, then BFS is a good choice. So as a general rule of thumb, you can remember whenever problem requires traversing nodes level by level, BFS can be used. These are tree structure, and in graph basically it is also connecting vertices and edges, but, and there is a relationship between one node to another node, but more or less for understanding we'll just use tree in this video. So how we can implement BFS? We can implement BFS with different data structure. Most properly is used queue because the base principle of queue is Whenever the data is added in the order, the same order, the data will be processed. So basically, in whichever order item is getting added into the queue, in same order it will be processed. So which is first in first out principle, and that is what is required in the BFS. So in the— if we convert this into an array, so it will look something like this. 1, 3, 4, 5, 6, and 7. So when this will be converted into the tree structure, so 1 will become a parent node, then it will— 2 will become a left child and 3 will become the right child and so on. So, and with queue principle, then whatever item is added first will be processed first. So first with BFS, when we write a code, first we'll use the 0th index, then first index, then second index, and so on. Okay, so we already spoke about what type of problems we can solve using BFS. So the shortest path, looking at the tree view, like if you want to look at the tree from the right side, like what all nodes are visible, we can use BFS. Or if you want to find the deepest level sums, we can do that, like zigzag problems, like Christmas tree problems. All of those can be efficiently solved using BFS. So zigzag problem is like from the top node we are going to the left to right. We'll go to 3, 2, then we'll go to 4, 5, 6, 7, and so on. So usually in BFS there are 2 code variations which I have found very useful, and I haven't seen a lot of code templates or other BFS topics very clearly explain about this, but I'll touch base a little bit on that. So there are 2 approaches, and first approach is shift-based approach where the item from the queue array— where we shift the item from the queue array and then process the node. So basically we'll just take out one from here and we'll just process this one first. And in this approach, we do not care about the levels as much because we are doing traversing node by node, but we are not considering level by level. So that one common example is deepest leaf sum where The last— once we reach the last level, we are just taking that answer and we'll ignore all of the above answers. So the second approach is where code needs to know about the levels. So basically, once all the nodes in one level is done, then code knows about it's in the next level, so it will do some logic before we proceed to the next level. So which I call a level-based approach, level-to-level approach. So in that, what we do, we calculate the length of the queue, then loop through the nodes in the current level, then do the logic and check if the current node has left or right child and add it to the queue. So a common example of this pattern is finding the maximum node values in current levels. For example, you have to find the maximum node value in first level because there is only one item, so answer is 1. second level, what is the maximum node here? It is 3. So then answer will become— we'll push 3 into the answer. And then in the last level, 4, 5, 6, 7, whichever— which is the highest number? 7 is the highest number. So that way we can— we know code— code knows that in which level it is working, and based on that we can write a logic. I'll share the code template here. And we'll also take a look at the problems further. So about the code complexity, so time complexity of BFS depends on the vertices and edges, so, or nodes and leaves, which holds the best average and the worst case. So we can say time complexity for this is Time complexity is O of visiting every node and edge is O and the space complexity is O because when we're adding into the queue, we are also basically visiting all the vertices, all the nodes. So I'll just add it here. City. Okay, so I already have a code template, so I'll just, I'll just write here. I'll just copy and paste so that video is not long. So this is the shift level first approach. Shift approach. So in this, basically what we are doing is, uh, we'll— and it's just a code template, not real solution, not solving a real problem, but it is just how we traverse the tree using BFS shift approach. So in this, once we get the root, root is of basically a tree node data structure, then if root is null, then we'll just return the answer. And then when we are— then we add the root in the queue and while queue is not empty, we are going to traverse the queue. So you'll see in this line we are just doing a shift which is basically just taking the first element from the queue to process as the base principle is first in first out. So first is added at the first place so it is getting processed first. So if node is there, it is just conditional check we are doing. If there is the value, put the value into the answer object, and then we are adding— we are checking if there is a left or right child, then add that, push that into the queue. So once it is updated, so it will push 2 and 3 nodes into the queue object. And that way it will keep on working. So in the next iteration, again it will go, it will do the— it will push, it will shift the second object, process it, add 4, 5, then it will go to the third object, and then it will add 6, 7. So that way it is working in the sequence. So in this shift approach, basically you're just taking the element as it is added and keep on appending to the existing queue. Till the queue has item. Now in second approach, which is level-based approach, I am saying in this one we are doing level-based, first few lines are same. So while— same thing, while there is object in the queue, we'll work on the queue object. So in this, first we'll calculate the length of the queue, which is our level size. Then we also create an empty queue object, and then we run the loop for i equal to 0 to i is less than the level size, which is the length of the current queue, right? And then once we are in this loop, then we'll pick the node and process the node. Same thing, if there is a value, we update our logic to whatever custom logic you have to do. Then we'll check if there is a node left and node right, and if there is a value, we'll just push, push it into the next queue. Right, so now next queue will hold our next set of objects for the queue. So once this loop is done, for loop is done, then we will— I think this is additional— then we will add the next queue into the queue object. So now again it will go process, do the same thing till the There is a value in the queue object, right? So in this approach, we know once this for loop is done, basically we have visited all the nodes in that particular level. So if we have to do any other logic here, which is level-based logic, we can do right here. So this is code templates. Both are almost same with just slight difference. Then we'll try to implement this and see how it will be, how it will work. Okay, so let's see this problem, binary tree right side view. So in this one, we'll try to First, read the, read the question. So given the root of a binary tree, imagine yourself standing on the right side of the tree and return the values of the node you can see ordered from top to bottom. Okay, it's not from, it's not from bottom to top, but top to bottom. Okay, so imagine there is a tree, you are standing here, and then what all nodes you can can see, that's what we have to return in the answer. So we'll see here, here is an array 1, 2, 3. Null means that there is no child for that, so it is making 1, 2, and 3, and then null. That's why 2 does not have any left child. Then 5, it's a right child. Then again null, we'll visit to the parent node 3. No left child and 4, which is a right child. Okay, so in this one, answer is 1, 3, 4. In example 2, we have 1, 2, 3, 4, 1, 2, 3, 4, 5. No child for node 3, and we don't have to worry about it. But now in this one, Answer, you'll see there is answer four and five also because if you're standing from here on the right side, you'll probably see these two also because you're looking from bottom to top, right? So one, three, four, five. Okay. From top to bottom. Okay. So so we'll solve this using a Using which approach? Right, so because problem is asking us to process level by level, and it also is asking once one level is done, then we should know which node is there, right? So if we need to know that, so level-based approach is is sounding default choice for this so that once code knows once one level is processed, then we have to go to the next queue. Okay, makes sense. Alright, so let's just start with the— and we are returning a number array. Let's just see. So first base condition, because root can be null. So let's just do if root is null or empty, then return empty array. And then let's just take number array, which we will return as the default, as the answer once all the code logic is done. And then here, let's take a queue. Now see, this is based on the template. I'm not doing anything additional in this one. I'm just saying take the— follow the code template, right? So now we know this one also. Now what is the next step in the code template? Once we have the root object created, assigned in the queue, now we'll have to run the loop till queue is not empty. So till queue has some length. Run this, work on this queue. All right, so now in this next step is we have to find the level size, which is queue.length. So this is our current queue length, which is 1. Okay, so now we need— so now once we are in that current level node, we also need to get the right side view of the value. Okay, so now in this current, in, in this current queue object, we just need rightmost node value. Which which will be what? Because we are working on the queue, which is nothing but an array. So we'll just do q dot length minus one and dot value. Well, this is the tree node structure is given to us. Value left and right. So why I'm doing this one? Because in the current node root, in the current queue. Okay, in array, how we take the rightmost value? So we are just taking the length of the queue minus 1 because array starts from 0th index. So the value will be 1 for the 0th index, right? When the first comes in the second time, second iteration, third will come and then fourth will come. Okay, now according to template. Now we need next queue object. Okay, so now once we have this, okay, we also can right away push the value in the answer because we have, we have already got, we have already got the value which we need in our answer object. But code is not done here. Now we have to process the queue node and put in the— put the next object in the queue. So how we'll do that? So let's go with this code template approach where again we are running a loop from i 0, i levelSize. which is the length of the current level, and i++. So now we only need to write const node equals to queue . Nothing but a simple array-based traversing we are doing. And now we are just checking if node.left has value, then push it into the next queue. If node.right, then push it into the node.right. Okay, right now what is the next step based on the template? Now we have next queue, next level nodes in this next queue, we'll just need to assign it to the queue and that's it. So now once next queue is processed, which is level 2 and 3, when it will come here, it will take the rightmost value, then again it will go do the same thing, assign next queue 5, 4, and then it will get the value to the queue. From next queue to the queue. So shall we run it? Oh, I have to log in. Give me a second. I'll just— okay, so I've logged in. Now let's run the Okay, seems like it all passes. So it's very simple. Same thing if you have to do from— for the left side view, we'll just change it to 0 because that's how our queue is managed in an array, right? So now that we have done this one one using level-based approach. Let's try to find one shift-based approach and we'll see. Okay, so for next code template, where we have shift-based approach. We can take a look at this problem. Not deepest level. Why it says zigzag level order traversal? Even though it is good for both type of code templates, but we'll see it with the shift-based approach. So what we have to do is we have given the root of a binary tree, return the zigzag level order traversal of its nodes' values from left to right, then right to left for the next level, and alternate between. So basically, when we are on node 3, then we have to go from left to right, node 20, then from right to left, node and then after that we'll go to the next level, then we'll go to from the left to right 15 and then 17 and so on, right? So if you see, this is the tree, then 3 is the value, then 20 and 90 right to left, then left to right 15 to 7. This is how we can do this, is basically same code template. We'll just run the queue till queue is empty, we'll take the node out and we'll have to just check the direction of the node in which it is there, and based on that, we'll put it into our level object, and then we'll just push it to the answer. So because root can be nullable, let's just return— let me do one thing. Result can be number, number. Let's just return result, and otherwise return result once processing is done. And then we are saying let q equals to root. But now, because this is also level-based approach, we need kind of a delimiter or a flag where we know that once this level has been processed, do some custom logic, right? So we'll just use null as delimiter. Okay, and then next requirement is we have to go left to right and right to left. So let's just call it left to right flag, and which is true because that's what the default traversing will do. So Okay, and then we need all the level nodes in the current level and then push that into the results. Okay, so while queue.length, just run the loop. I did the typo here. Length, run the loop. Then we are saying give us the node first. So what is the shift-based template approach? Get the first node out. Now we'll check if node is not empty, then we'll check if is left to right. Oops. If it is left to right, then we'll basically pushing the value in the level nodes. Okay, so what is the value? .value. Now if it is not left to right, if it is from right to left, then how we'll do that? Pause and think. Do we do push? Push basically puts it the end of the array. How we can put it in the front of the array? Any, any existing method? Yes, like we are doing shift to take the first out, we can do unshift and it will put the value in the front. Okay, and now the remaining template logic. If node.left is there, then we are just saying let's push in the queue. See, that's the difference. In level-based approach, we take a next queue object usually and push that, but now because we are doing a shift-based approach, we took the node out. We are not running any nested loop to traverse the nodes in the levels, and then we'll check node.right and then queue.push node.right, right? So now this is the part which is, which is common in our template, but we need to— in this, so far we have just checked if node is there and if direction is this, put it into the level nodes. And then push left and right node values if they exist in the queue. But what happens? We added null also. What happens when we reach null? So if node is empty, then we need to do the custom processing which is required that level is over basically because node is empty. First is root is processed and then after null node.left, which is 9, and node.right, which is 20, has been added in the, in the queue. So what is the structure now? Null, and then we have 9, and then we have 20, right? So now in the next iteration, when we comes here, when code comes here, line 25, it will check if node is there. No, it's is not there, then it will come here, and here that's where we have to push the current node value. I'll just copy this current node levels into our result answer— result object. And now same thing, now we'll have to reset this so that in the next iteration when we go, it knows That it is not duplicating basically and just creating a new set of answer. And then we also need to do a couple of more things. We already did left to right. Now what should be the scenario here? Now just toggle it to false, or if it is false, toggle it to right. So the direction is maintained at every level. Right, and now we also need to add— we added null in the beginning. Now this level has been done, we already have 9 and 20. Now null is not there because we have already did the shift over here. So now, but we need to add null again. For that, what we're gonna do, if we don't need to— we, we need to check if q.length is there, basically if there are more nodes to process, then add null. If there are no more nodes there, we should not be adding this line, otherwise it will keep on running in the loop and our method will timeout. So to break the delimiter, to break the execution We are checking if there are no more values in the queue, don't push the null. If there are values in the queue, push the null so that we can put it into the answer. Okay, so again, in shift-based approach, we just take the first item from the array, put it into the node. We're putting in the node, then we are checking if left or right child exists, push it into the queue, same queue, and then keep on processing it. Rest everything is custom logic depending on the type of problem we are solving. Okay, so now let's try to run it. Seems like it works, right? And it's a medium-level question in LeetCode. But you see, based on these generic templates, how we can break down the problem, understand the pattern, and depending upon the requirement, you can just choose which one works best. So when BFS— when tree traversal-based question comes, take a look at the requirement whether it is asked for level-by-level processing. Then yes, if yes, go for BFS. Otherwise DFS maybe is the good, good choice. Now once you have identified, okay, it can be solved through BFS, then in BFS, which out of which shift-based or level-based approach which can be easily used? Most of the time you can use either/or approach, but sometimes it is just easier with reduced complexity. It's easier to just use shift-based approach or level-based approach. Okay, right. So also we have, it's, we have a GitHub repo. It is not, we are not trying trying to replace or introduce anything additional, but if you want any technical interview preparation guidelines or kit, basically in this repo we have summarized from the different platforms like LeetCode, NeetCode, and Hello Interview and other available tools for interview coding, coding interviews. So this repository is free, you can take it. I'll just launch it here. So it's a free GitHub repo, you can clone it, fork it, and basically just to start using it. We have a quick start, how you can do it, how to use this repository. It gives you patterns. So basics will give you like what are some basics before you even deep dive into the code, some system design level things which is more focused on system design rounds, not for coding rounds. Then you can learn about complexity calculation and data structure, then the patterns and Then there are algorithms, there are exercises. So go through this, you may find it helpful. We are using Vitest. You can just add as many test cases, run, test your method and see how it is performing. Okay, so it's a compiled list. I know there are a lot of resources out there, so don't want to confuse you more. But if it is something you find useful, just give it a star and fork it. Then just create your own checklist. Like we have created some checklist for every coding interview. You can quickly go through bigger complexity, like you have practiced common patterns which are already there. So review notes if you have taken any notes, review common problems so that there is a quick revision and you're not juggling through different platforms. Platforms and tools, right? So yeah, just go through it. And shout out to the community and all the existing creators who have created so many good content out there. But yeah, that's all. Thank you.