Breadth-First Search

[00:00:00]
>> All right, so let's talk about a breadth first search. I am gonna create a new file just because that's gonna be a lot easier. I hope everybody has enjoyed the use of good GNU Image Manipulation Program. It means I'm super open source, I'm a fosse supporter clearly.

[00:00:20]
Okay, anyways, so, a breadth first search, let's just redraw our tree. I can't remember all the numbers, but I know that there was a 23, a 5, a 4, and I forgot what this side was, so I'll just make it up. An 8, a 21 and a 15.

[00:00:36]
All right, so a breadth first search is kinda like the opposite of a depth first search. So first off, can anyone just guess the data structure we're gonna use if it's the opposite of a depth first search.
>> Queue?
>> Boom, Queue, that's exactly right. My goodness. Graham, that was great.

[00:00:57]
So yes, the opposite of a stack, a queue, of course. And that's what we're gonna be using the reason why it's an opposite, of course stack is first in last out versus a queue being first in first out. So that's exactly what we're gonna be using. So if you think about this, what a breadth first search is gonna do is it's gonna visit this node.

[00:01:15]
Then it's gonna visit this node, then this node. Then it's gonna visit this node, this node, this node, this node. In other words, it's a tree level kind of visiting. You'll visit one level of the tree at a time. And this is true even if the tree is kind of sparsely populated, even if it's just a bunch of little lines and then maybe every now and then a parent with two and then keeps on going.

[00:01:38]
It will always follow the level of the tree, each iteration. I was once in an interview, and I never heard the term tree level traversal, but I was in an interview and the interviewer was just like, all right, can you print out the tree in tree level ordering?

[00:01:52]
And I was just like, never heard of this, can you please explain this? And they're like, well, you start here, and then you go to here, and then you go to here. And this is promptly where I corrected my interviewer saying, first off, that's not a real term, it's called a breadth first search.

[00:02:07]
And second off, you shouldn't say that cuz it's incorrect. And I got the job but nonetheless, argue with your interviewer if they're incorrect, it's just the best way to go. That may or may not be a pro tip. I'm just saying that that may not actually work out for you but it worked out for me, but it was fun.

[00:02:21]
I was also kind of a jerk when I was younger, it just happens, I don't know. Anyway, so how does this work? How do we visit this? Let's draw this out again except for let's draw it out using a queue. So if we start at 7, let's see, how do we do this again?

[00:02:37]
Yeah, the arrows go this way. Arrows go backwards or arrows go forward. I always have to rethink about this. So we start at seven, right? And we're going to add 23 and 8, right? 23, 8, awesome. And then we're gonna pop off 7. So now our head is pointing to 23.

[00:02:57]
Then obviously we printed out 7 at that point. Now we visit 23. So 23 has two children, right? 5 and 4. So we're gonna add 5, then 4. Then we're gonna print out 23. Then we visit 8, what does 8 have? Well, 8 has two children. So we're gonna visit these two and we're gonna put in, let's say, 21.

[00:03:20]
My goodness, way too small, sorry. And 15, there we go. And then we're gonna print out 8. We'll visit 5, 5 has no children, we'll print out 5. We're gonna visit for 4, 4 has no children, we're gonna print out 4. We're gonna visit 21, 21 has no children, print out 21.

[00:03:38]
Visit 15, 15 has no children, 15. Now notice the order of this as I printed it out. It was a 7, it was a 23, it was an 8. it literally went exactly how I drew it starting from the left hand side to the right hand side. Obviously, we could reverse the direction in which it reads by pushing in first the right hand side then the left hand side, but again, strange, always go left to right.

[00:03:59]
Why that is, I don't know. There we go. So that's all it really is, and we can do that pretty easily. And we are gonna do it but we're gonna be using a JavaScript array list as our queue. If you have it from yesterday, you could technically use the queue you created yesterday to run this, but we'll just pretend as if it is a queue.

[00:04:18]
And I guess one thing before we do that, what is the running time of a breadth first search? The running time, of course, of a breadth first search is going to be order n. But if we actually use a JavaScript array, it's no longer going to be order n, it will be order n squared.

[00:04:38]
You're probably thinking, how's that possible? Why is that the case? Well remember, what's the thing about array lists? Array lists have getting at order 1. It has push pop at order 1, but shift and unshift, right? That was order n. You remember that from yesterday, right? If you push and pop from the beginning of the list, it has to reorder all the following elements.

[00:05:08]
Now you're thinking well, but the queue is not necessarily gonna be that full, right? So is it really that? Practically speaking, is it really gonna be that? The thing about a binary tree, especially if it's a full tree, what you're gonna notice is that when you're right here, you have one item in the queue.

[00:05:24]
When it adds its children, it will have two items in the queue, right? When we get through this level of the tree, we will have four items in the queue, or half of the entire tree in the queue. If there was another complete level to this tree, if we went through all of this, we would have eight items in the queue or approximately half the tree, technically half plus 1 if I'm not mistaken, cuz 4, 2, 1 is 7, now we have 8.

[00:05:53]
The thing about a binary tree is each level, if complete, is approximately half the size of the entire tree above it. So as you can see, if we had to do half the tree shifting off, we'd have to do an n amount of work n times. So n squared, there you go.

[00:06:11]
So make sure you use the right data structure. Don't just use something cuz it's convenient. You really should use a queue when properly implementing a breadth first search or else you're gonna get some terrible running times. Just a thing to know.