Breadth First Traversal

English [Auto] Now, one of the most interesting things that you can do is to visit and process it. We know that there are a whole variety of ways in which this can be done. Visiting and processing ultimately is called families. There are two types of Traviss breakfast, and then in this lecture we take a look at how breakfast. We've just learned about the structure of a binary tree. Now let's hear about the things that are actually interesting about a binary tree in the case of a a stack. What was interesting from a user perspective, if the behavior of a Q and A stack when we pushed and popped elements of it and killed and discovered elements in the case of a binary tree, what is really interesting about it is how the nodes of a binary tree can be visited and processed. This is binary tree traversal, binary tree traversal can be done in a whole variety of ways and they are very interesting because they lend themselves to interesting problem solutions. So what's really about interesting about binary trees is the number of ways in which we can visit the nodes of a tree. So what's different about the different ways that we visit the north? How big is it the north of a tree can vary based on the order in which the nodes are accessed. The way we visit the North can give rise to a different sequence of Naude ideas based on the order in which we access them. These different orders in which we accessories give rise to different algorithms, which find different use cases in the real world when we are solving problems. That is why it's interesting to study these algorithms by which we visit all the node of a tree in a different order. Visiting the node of a tree and processing these nodes is called Ravil Think Atley. There is a subtlety here, I spoke about visiting earlier, but what I really meant, what we process the node of a tree in all the algorithms that we'll see. So from now on, will notice that we might visit a node more than once, but process a node exactly once. It's the order of processing that's important and amusing, visiting as a substitute for processing A.. It's important to realize this difference because it's the processing of the node that really matters. It's totally possible to access a third node to process it. We have to go through the second node. The third note, when it's processed, that is the important operations that we worry about. So getting back to what we are talking about, processing the nodes of a tree, visiting them and processing them is called reversing a tree, and there are two main ways in which it can be done. The first is called Brett First. Breakfast essentially means that you visit all nodes of a level before moving on to the next level, all nodes at a level from the breath of a tree. So we access every node in the breath first before moving on to the next level. This is called Brett. First traversal of a tree. The other broad category of tree traversal is called first. This means we reach into a tree as deep as possible, get to a leaf node and process that. How we go deep into the tree, that's another question for a later lecture, we'll be talking about breakfast traversal where we access all nodes in a particular level before moving on. Don't worry, before the binary tree lecturer's out will have spoken in detail about both breakfast algorithms as well as first algorithms. Let's first take a look at how breakfast first traversal of a tree works, Brett first involves visiting all nodes at a certain level. Before we move on to the next level, all nodes at a certain level have to be visited and processed before the algorithm can move on to processing nodes at the next level. If you go back and remember all the things we learned about a binary tree, we spoke about nodes at a level being siblings. So all siblings have to be processed before moving on to the next set of siblings at the next level. So what do we start with, the bigly all algorithms which involve traversing a tree or involve a tree in general? Start with the root node, the root node is the one node using which we can access all elements of a tree, all nodes of a tree are accessible from the node. So even for breakfast traversal, we start with the root node. The root node is at a level zero and is the first node that we visit and process. Going back to our levels, remember that the level basically. Defines the distance from the route not nor that level one hour, one hop away from the route, not node, that level two or two hops away from the route. Not since the route known as zero hops away from itself. It is said to be at level zero. Obviously, once the root note is done, we check to see if there are any other nodes at that level and visit and process them. Obviously, the root node is the only node at level zero, that's just the structure of the tree. So once we process the root node, we move on to its children, which are at level one. They can be at the most to know that. Level one, we have to process both of those nodes. And only one, if there's just one not available, obviously, but we have to process both of those nodes at level one before we can move on to the nodes at level two to process them. Once we are completely satisfied that the level has been exhausted and there are no other Nords to visit and process at a certain level. Then is when we move on to the next level. So if both the children of the route have been processed or however many children it has has been processed, then we can move on to level two and process all the nodes that. We continue this, every node of the tree has been visited traversal involves visiting and processing every node of a tree. So we continue this breakfast travel that is the traversal that is visiting and processing every node at a certain level. We keep moving up a level. Still, every node of the tree has been visited. All this was talk, let's see how breakfast traversal works and let's see it in a visual B so that you can really understand what's going on. Let's look at how breakfast traversal works rather than just talking about it. So here we have a binary tree. We are going to be working with this tree a lot. So you'll see a lot more of it in the coming years. What is the part that Brett, first traversal, because we know it starts with the root node, which is E! It flew down to the left, then moved sideways and flew down to the left again, move sideways. Flew down to the left and moved sideways. Note that it completes visiting all nodes at a certain level before it moves on to nodes at the next level. So B and C, which are at level one, are visited one after the other, only after C is complete. Do we move on to the. After the decomp and then we move on to the north, that the next level, which includes F, which is a child of the that doesn't matter. It's the note that the same level which. So the process will never end before moving on to level and plus one then and plus two, and then finally we end at the highest level, which in this example is level three. We start with a big note at the root, which means we start at Naude e. So let's visit Nordea. Now, there are no other nodes at the same level of aid because it's the LoopNet. Node B is the next node that we have to visit, node B is at level one. One thing to notice here is that we typically visit nodes which are the left before nodes at the right. So we move from left to right for the nodes which are at the same level. B is the leftmost node at level one, which is why we visit the next. Used the green color to denote nodes which we've already visited and processed. So it is Mark and. The next note has to be at the same level. The only option here is see. At the bottom, right, we'll keep a tally of the nodes we've already visited and processed so far, we've just got E in the list. We visit seat three is the next, not that level one, and we see now that there are no other nodes that level one, we can now move on to the next level. Remember that we go to the leftmost node and the next level first. So the division between B and E is the. The north we visited so far, and so we're keeping a track at the bottom. Let's go on and visit the. All right, be is at level two and is the first node that we visit at level two. It's the leftmost not. Now it's time for us to continue with this breathless search, and the next note will visit will be. The notes we've seen so far in order are E, B and C. You're keeping track at the bottom. We visit. ABC and the other notes that we've seen so far. It's time to move on to the next level. And the leftmost note is, if you that level three in this binary tree. No, we've seen so far A, B, C, D, and E in that order. In breakfast travels, the next node we visit is H. There's just one node left, it is the right child of E note that we've completely ignored who the parent nodes are when we do breakfast, said the only look at sibling nodes and move from one sibling node to another. Finally, we visit Jean. This is the last node in at least. We've seen all north through to H and we're currently processing Gene Autry traversal in a bratwurst manner is now complete. Toyoda's the final order in which we visited the Nords a, b, c, d, e, f, g. Now that we visualised that first traversal and know exactly the path that it takes, two or three, let us go about implementing it, the algorithm involves starting from the route. We use a here. Yes, we use some of the data structures we're already familiar with because it lends itself very well to the problem to be solved. What we want in the case of breakfast traversal is that the node added first to the queue should be the first to be killed, which is why AQ books we at the root node to the Q and then set up a loop to basically process nodes from the Q. Before the U.N. process, the node, which will initially be the route node after we've processed it, we add its children to the queue, making sure we add the left child first, adding the left child first is important so that we traverse the siblings from the left to the right. We continue this process so long as the queue is not empty. If you sit down and think about it and maybe work it out with pen and paper, you'll notice that the notes get added level. From left to right to the to the at the root node. And then it left and right. When we process the left child, we add its left child and the right. We continue this, this means the Nords get added level rise from left to right to the. This also means that the nodes are being used and processed in the order from the left to right and nodes at the same level will be exhausted. First, work it out with a pen and paper. You'll see that it works out perfectly. Let's see what the code for breakfast traversal looks like. We use a cue that we built earlier in some of our lectures. Take a look at the code on screen. The very first thing we check is that the root of the tree that we've been passed in is not enough. Another route basically means that there's nothing to traverse, we simply return. There is no breakfast. Trevathan also note that this is an iterative algorithm. It is not a recursive. We simply push and do things and give them all in a while. We saw start up by setting up a queue, holding nodes, and in the route, we know the route is a valid value, it's not null. So we knew the route. We set up a while loop, which processes the node in the queue, so long as the queue is not empty when we kick it off. We have the root node present in the queue. So we enter this while loop. Within the wire loop, we process the head of the queue, we become the first element and our processing is basically just a print statement. We are just printing at the screen and then we add the left side, followed by the right side. We end it on the cue. This ordering is important so that the next level gets processed from the leftmost nodes first to adits left child and right child to the. So we are filling up the queue and we are checking that it's not empty and processing all logs when there are no more children to process, the queue will be empty. We will have processed the last node in the tree.