1 00:00:00,410 --> 00:00:04,730 ‫So now we're going to write the code for breadth first search. 2 00:00:04,850 --> 00:00:12,200 ‫So I'll bring up our tree and I'll shrink it down into the corner to make room for our code. 3 00:00:12,500 --> 00:00:19,910 ‫And the first thing that we'll do in this function is create the Q called my Q and I'll bring that in 4 00:00:19,910 --> 00:00:20,930 ‫on the bottom. 5 00:00:21,610 --> 00:00:26,650 ‫And then we'll push the route into the queue like this. 6 00:00:26,950 --> 00:00:33,520 ‫And as we discussed in the last video, we're storing pointers to nodes, but we'll think about this 7 00:00:33,520 --> 00:00:36,310 ‫as storing a node in that queue. 8 00:00:36,490 --> 00:00:43,330 ‫And also, as we did in the other video, I'll change that node to look like this and then that will 9 00:00:43,330 --> 00:00:45,640 ‫bring us to our wild loop. 10 00:00:45,820 --> 00:00:51,310 ‫So we're going to run this while my queue size is greater than zero. 11 00:00:51,310 --> 00:00:55,000 ‫So in other words, this will run until the queue is empty. 12 00:00:55,270 --> 00:01:00,600 ‫And that's why we need to push the route into the queue before we get to the wild loop. 13 00:01:00,610 --> 00:01:03,880 ‫Otherwise this conditional will be false. 14 00:01:04,210 --> 00:01:10,600 ‫So I'm going to move this wild loop up and the first thing we'll do in the wild loop is we'll say current 15 00:01:10,600 --> 00:01:10,960 ‫node. 16 00:01:10,960 --> 00:01:12,790 ‫This is a pointer to a node. 17 00:01:13,060 --> 00:01:16,390 ‫We're going to set it to be equal to my queue front. 18 00:01:16,390 --> 00:01:21,280 ‫So we're setting an equal to this, which is this node. 19 00:01:21,640 --> 00:01:24,670 ‫So current node is going to move through the tree. 20 00:01:24,670 --> 00:01:31,840 ‫So whatever the current node is, I'll colour it green and then we'll say my queue dot pop and we're 21 00:01:31,840 --> 00:01:39,400 ‫going to remove that from the queue and then we'll say see out current node value. 22 00:01:39,700 --> 00:01:45,130 ‫So that current node value is 47 and that gets output to the screen. 23 00:01:45,430 --> 00:01:53,290 ‫So in addition to using the value we're going to use left and right from that node, so we'll say if 24 00:01:53,290 --> 00:02:01,570 ‫current node left is not equal to null pointer, and you could just write this as if current node left. 25 00:02:01,840 --> 00:02:09,010 ‫And what this is saying is if current node left is pointing at a node and in this case it is is pointing 26 00:02:09,010 --> 00:02:10,750 ‫to that 21 node. 27 00:02:11,470 --> 00:02:20,080 ‫We're going to add that node on the left to the Q and then we'll do the same thing on the right and 28 00:02:20,080 --> 00:02:23,260 ‫add the node on the right to the Q. 29 00:02:23,710 --> 00:02:29,860 ‫So to speed this up, these three lines, I'm going to combine moving forward. 30 00:02:30,130 --> 00:02:35,860 ‫So that first line we're going to set current node to be equal to my Q front. 31 00:02:35,860 --> 00:02:41,200 ‫That's this node here, which is this node in the tree. 32 00:02:41,620 --> 00:02:48,640 ‫And then we're going to remove that from the Q and then we're going to output current node value like 33 00:02:48,640 --> 00:02:49,090 ‫this. 34 00:02:49,090 --> 00:02:53,530 ‫And like I said, moving forward, I'll just combine that all into one step. 35 00:02:53,680 --> 00:02:59,950 ‫But now from the 21 node, we're going to look to the left and if there's an item there and there is, 36 00:02:59,950 --> 00:03:07,750 ‫that 18 node will add that to the Q and then we'll look to the right and add that 27 node to the Q as 37 00:03:07,750 --> 00:03:08,410 ‫well. 38 00:03:08,830 --> 00:03:16,060 ‫So now we'll run these three lines of code which outputs that 76 and makes the 76 node, the current 39 00:03:16,060 --> 00:03:16,690 ‫node. 40 00:03:16,990 --> 00:03:24,850 ‫And then we'll look to the left of the 76 node and add that 52 to the Q and to the right of the 76 node 41 00:03:24,850 --> 00:03:27,820 ‫and add the 82 node to the Q as well. 42 00:03:28,530 --> 00:03:35,250 ‫So now the items that are left in the queue are going to be these nodes at the very bottom of the tree, 43 00:03:35,250 --> 00:03:37,350 ‫which are all leaf nodes. 44 00:03:37,950 --> 00:03:44,970 ‫So we'll run these three lines of code which outputs the number 18 and makes the 18 node the current 45 00:03:45,000 --> 00:03:45,690 ‫node. 46 00:03:45,930 --> 00:03:50,460 ‫But the 18 node doesn't have anything on the left or the right. 47 00:03:50,460 --> 00:03:54,120 ‫So we'll just move to the 27, same as true here. 48 00:03:54,270 --> 00:03:59,400 ‫And that is the case for the 52 node and the 82 node as well. 49 00:03:59,820 --> 00:04:05,100 ‫So now our queue is empty and that breaks us out of this wild loop. 50 00:04:05,550 --> 00:04:12,570 ‫So now I'll remove the queue and we have now output all of the values from the tree. 51 00:04:13,110 --> 00:04:16,350 ‫So now I'll add this in with the rest of our code. 52 00:04:16,710 --> 00:04:19,440 ‫We'll look at this code in a moment in vs code. 53 00:04:19,440 --> 00:04:25,170 ‫And when we do we'll create this tree and we'll run breadth first. 54 00:04:25,170 --> 00:04:29,370 ‫Search on that and we'll expect our output to look like this. 55 00:04:29,880 --> 00:04:33,240 ‫So now let's flip over and take a look at this. 56 00:04:33,780 --> 00:04:38,550 ‫So to begin with, I want to point out that we'll need this include statement because we're using a 57 00:04:38,550 --> 00:04:41,070 ‫Q and I'll scroll up. 58 00:04:41,280 --> 00:04:46,770 ‫And I also want to emphasize that this is a member function that has been added to the binary search 59 00:04:46,770 --> 00:04:48,150 ‫tree class. 60 00:04:48,780 --> 00:04:55,530 ‫And I'll scroll up again and this is the breadth first search member function that we just created and 61 00:04:55,530 --> 00:04:57,060 ‫I'll scroll up again. 62 00:04:57,480 --> 00:05:01,590 ‫And in our main function, this creates our new binary search tree. 63 00:05:01,590 --> 00:05:07,470 ‫And this creates all of the nodes, just like we had in the diagram and the width. 64 00:05:07,470 --> 00:05:15,510 ‫This line will run breadth first search and I'll run this and we have output the value from all of the 65 00:05:15,510 --> 00:05:18,090 ‫nodes in the order that we expected. 66 00:05:18,930 --> 00:05:23,970 ‫And that is our function for breadth first search.