This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Breadth-first Traversal" Lesson
[00:00:01]
>> Brian Holt: This was depth first traversal. They were kinda variations on the idea of depth first traversal. But something that you wanna keep in mind with depth first traversal is what you're trying to do is you're actually trying to get as far away from the root node as possible as quickly as possible.
[00:00:17] You're trying to process nodes more towards the leaves. When I say a leaf I mean, something like down here at the bottom of the array. Something that has no children at all. That's what depth first traversal really excels at is getting as to leaves first getting away from the root node as possible.
[00:00:34] Getting away from the root node as fast as possible. That's not always how you want to process a tree, though. Sometimes you wanna process the nodes closest to the root as quickly as possible. So that's when we enter into something called breadth first traversal. So in this particular case what we wanna do is we wanna process 8, and then we wanna process 3, and then 10.
[00:00:58] So we wanna be processing things, almost like one layer at a time. We wanna be processing things closer to the root node. And depends on what kinda problem we're trying to solve that we'll choose different algorithms, but that's the tradeoff that we'd be making there. Depth first as like I wanna get away from the root node, breadth first, I wanna stay close to the root node.
[00:01:20]
>> Brian Holt: So if we're going down here, yeah, let's actually talk about what order we would get out of breadth first traversal in this BFC. Again, typically you would not use breadth first on a BFC, that's doesn't really make a ton of sense but to illustrate what's going on here, let's talk about it.
[00:01:37] So if I was gonna process this tree using breadth first traversal, the order I would get out of it would be 8, 3 10, 1, 6, 14, 4, 7, 13. You just go one layer at a time left to right. Make sense? So conceptually I think that makes sense.
[00:01:58] The actual implementation of it is interesting. We'll go with that. We're gonna use our old friend the queue if you don't remember queues, again, that's talked about in part one but to give you the short version of a queu, it's like a que for those of you that are [LAUGH] British and a line for the rest of us that are in the US.
[00:02:22] First in, first out. So if I enter the line first to go on the ride at Disneyland, I'm gonna hopefully be the first person on the ride. That's kinda the same idea here is when you put things in the queue, the longer that it's been in there, the more towards the front that it's gonna get until eventually in the first in the line, and then it would go.
[00:02:38] That's what a queue is. What you're going to do when you're processing something using breadth first traversal is you're going to add eight into the queue. Then what you're gonna pop the first thing dequeue, I say papa. Well, let's go with dequeue. You're gonna dequeue first thing off at the queue and process it.
[00:03:02] Then you're going to add its left child and right child to the queue. And that's what you're going to keep doing. Is you're gonna just take something off the queue, add the left child, add the right child to the queue, and then process the node. So I'm gonna add eight.
[00:03:17] I'll process that. And I'll add 3 and 10 in there. Then I'll go down to 3, cuz I'll dequeue the next one which will be 3. i'm gonna add 1 and 6 to the queue, process 3. And then at that point, I'm gonna dequeue the next thing. What is the next thing in the queue?
[00:03:36] 10, right? Because I queued that up here. So I'm gonna go down over here to 10, I'm gonna process 10 and then I'm going to unqueue its left and right child, it has no left child, but it has a right child. So I'm gonna unqueue 14. Then I'm going to dequeue the next thing in the queue so what's the next thing I'm gonna process?
[00:04:00] 1, because I unqueue that over here at 3. Does that make sense? Yeah, go ahead.
>> Speaker 2: So will you just clarify the order of adding to a queue, dequeuing and processing again, what?
>> Brian Holt: I'm probably mixing it up cuz it really doesn't matter. [LAUGH] So as opposed to the depth first and which is probably where this is getting a little muddy, that's my fault, I'm sorry.
[00:04:29] It doesn't actually really matter because you're gonna be processing something, and then you're gonna be enqueueing both of its children. And then you'll just go into the next iteration. And what order that happens in your particular function doesn't particularly matter. Is that a sufficiently vague answer? [LAUGH] Yeah, hopefully that makes sense once you actually start writing the code.
[00:04:50] But at some point, you need to process the node. And then you need to add the two children to the queue. What order you choose to do that in should not particularly matter. And that's a great question. Thank you. You can write this recursively. It's somewhat makes sense to write recursively if you like to do that.
[00:05:13] It's also fairly easy to write just using a while loop. So you just have a wild look that just goes through. And while there's things in the queue, you just process the next thing in the queue. And that's another easy way to do it, as well. I will show you both, so you are welcome to go and write it either way that makes sense to you.