1
00:00:00,450 --> 00:00:06,540
‫So in this video, we're going to do our introduction to Breadth First Search.

2
00:00:06,870 --> 00:00:08,660
‫So I'm going to bring up a tree.

3
00:00:08,670 --> 00:00:14,850
‫And if you recall from the last video breadth first search is the one where we start at the top and

4
00:00:14,850 --> 00:00:16,740
‫then we just go row by row.

5
00:00:16,740 --> 00:00:21,900
‫So we'll do the two items in this row and then we'll do the items in this row.

6
00:00:22,510 --> 00:00:24,390
‫So I'll move this over.

7
00:00:24,400 --> 00:00:27,100
‫And in order to do this, we'll need a queue.

8
00:00:27,130 --> 00:00:33,970
‫I'm going to call this my cue and we're going to start out by storing the route in the cue.

9
00:00:34,240 --> 00:00:41,410
‫Now, technically, this cue holds pointers to nodes, but think of this as actually storing the node.

10
00:00:41,920 --> 00:00:49,600
‫So remember that the node has three attributes value left and right, and we'll be using all three of

11
00:00:49,600 --> 00:00:50,230
‫those.

12
00:00:50,680 --> 00:00:56,200
‫So visually, I'm going to change that node in the queue to look like this, but I'm going to keep it

13
00:00:56,200 --> 00:01:00,190
‫the same color to emphasize that we're storing the node.

14
00:01:00,610 --> 00:01:06,130
‫So remember I said that we would use value left and right, all three of those attributes.

15
00:01:06,130 --> 00:01:09,790
‫So we'll start out by doing a see out with the value.

16
00:01:10,090 --> 00:01:17,500
‫But then for left we're going to look to the left and there's that 21 node and we'll add that to the

17
00:01:17,500 --> 00:01:18,130
‫queue.

18
00:01:18,490 --> 00:01:23,770
‫And then to the right is that 76 node and we'll add that to the queue.

19
00:01:24,160 --> 00:01:29,710
‫And once we've done that, we'll do a see out with this value and then we'll look to the left and to

20
00:01:29,710 --> 00:01:32,020
‫the right of that 21 node.

21
00:01:32,530 --> 00:01:37,030
‫So on the left is the 18 and to the right is the 27.

22
00:01:37,330 --> 00:01:43,090
‫And then we'll do the same thing with the 76, and then we'll look to the left, and that's the 52 node,

23
00:01:43,090 --> 00:01:45,850
‫and to the right is the 82 node.

24
00:01:46,210 --> 00:01:52,840
‫So now we'll do this 18 but that 18 node doesn't have anything on the left or the right, so we'll just

25
00:01:52,840 --> 00:01:54,000
‫move to the next one.

26
00:01:54,010 --> 00:02:01,690
‫The same is true here and also for the 52 and the 82, and then we're only going to run this until the

27
00:02:01,690 --> 00:02:03,280
‫queue is empty.

28
00:02:03,850 --> 00:02:08,170
‫So I'm going to take these numbers and I'm going to move them down and show you something else that's

29
00:02:08,170 --> 00:02:09,730
‫interesting about breadth.

30
00:02:09,730 --> 00:02:10,750
‫First search.

31
00:02:10,750 --> 00:02:17,350
‫I'm going to move this 47 up here and these next two numbers up here and with breadth.

32
00:02:17,350 --> 00:02:22,660
‫First search, you get this exact order of the original tree.

33
00:02:23,140 --> 00:02:25,330
‫So we'll code this in the next video.

34
00:02:25,330 --> 00:02:30,070
‫But for now, that is our introduction to Breadth First Search.