Breadth First Tree Traversals

[00:00:00]
>> We just did depth-first traversal. So let's hop down here and do breadth-first traversal. Going back to our little fun tree here, same tree, what if I want you to look at the nearest nodes first, right? So that, the nearest nodes to 8 are 3 and 10. And then 1, 6, 14, and then 4,7,13, right?

[00:00:24]
So we're actually moving down level by level, right? This is called a breadth-first traversal because we went for breadth first as opposed to those which were going as deep as possible first. Now we're trying to go as close as possible first. Okay, so a breadth-first traversal of this array is going to be 8, 3, 10, 1, 6, 14, 4, 7, 13.

[00:00:59]
So how do you do that? Well, we're gonna do it with a queue. So a queue, if you remember, the first item that you add to it is the first item that you get out of it, right? It's kinda like standing in line, right, the first person who stands in line is the first person that gets on the ride or on whatever.

[00:01:22]
So what we're gonna do is we're going to add 8 to our queue. And then we're going to pull off 8, add it to our array, and then we're going to enqueue both of its children. So we're gonna to add 3 and 10 to our queue. We're then going to process 3, right?

[00:01:40]
And then we're going to enqueue both of it's children. So our queue right now will be 10, 1, 6, right? So on and so forth. Every time that you pull a node off, you're gonna grab its value, you're gonna add both of its children to the queue, and then just keep processing until the queue is empty.

[00:02:00]
So, start by adding 8 to the queue like this. Process 8, and when I say process, I just mean add it to the final array, right? So we process 8. So we add that to the final array which is equal to 8 right now. And then we enqueue 3 and 10 to the processing queue.

[00:02:23]
So we have 3 and 10 in our queue right now. We're going to dequeue 3, which is the first item in the array. And the queue right now is just gonna be 10. We're gonna enqueue 3's children. So we're gonna have 10, 1, and 6 in our array right now in our queue, and we're gonna add 3 to the final array.

[00:02:45]
So we have 8 and 3. Okay, we're gonna dequeue 10, this one here. Dequeue 10, so the queue right now is just gonna be 1 and 6. We're gonna add 10's children to the queue. So, it's gonna be 1, 6, and 14 in the queue. And we're gonna add 10 to the final array here.

[00:03:09]
So we have a 8, 3, 10, right? 8, 3, and 10. We're gonna dequeue 1, which is the first one in here in the queue of things to process. And the queue now is just 6 and 14. We're gonna dequeue 10, we did that. We're gonna queue 1's children.

[00:03:29]
I doesn't have any children, so nothing gets added. We're gonna then add 1 to the final array, we end up with 8, 3, 10, and 1, right? And I hope you're seeing the pattern here, which you pull off an item of the queue, you add it to the final array, and then you enqueue it's children.

[00:03:44]
And you just keep doing that. It's not recursive, it's iterative. And you just keep doing that until you've gone through everything in your queue. So again, our final array here will be 8, 3, 10, 1, 6, 14, 4, 7, 13. So you might ask now, why is this any different or better than depth-first traversals, right?

[00:04:09]
Why do I need to learn four different ways to traverse things? Well, this is really good for nearness, right? What if I wanna find, I don't know, the nearest 6 to the 8, right? Now, if I was doing depth-first traversal and I had a 6 way down here that was super deep in the array, I would find that one first, right, because depth is gonna go deep first.

[00:04:34]
So you need to do something like breadth-first traversal. This actually ends up being one of the more useful ones that I'm teaching you, because we're gonna do pathfinding and graphs here in just a second, which use breadth-first traversal quite a lot. So if this isn't quite concrete why this is useful, believe me, in the next two lessons, you're gonna find out very concretely why this is useful.