This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Tree Queue Diagram" Lesson
[00:00:00]
>> Speaker 1: Oscar asked, can you please explain how the trie becomes a queue, and can you show it on the board how the queue works?
>> Brian Holt: Yeah, sure. Let me move this out of the way real quick.
>> Brian Holt: Can't believe someone actually wants to see me draw.
>> Brian Holt: All right.
[00:00:26] So let's do a new blank page. So let's just do.
>> Brian Holt: We're gonna do A up here, and then we're gonna do B, C, D, E, F and G. Now I know my A B C's. Okay so, this is a trie. I purposefully did the letters in that order so that you'll see that that's the order that they're going to go into the array.
[00:01:06] Spoiler alert. The first thing that you're going to do is you're going to add the root node which in this case is A, to the queue. So we're gonna have a queue that's going to be just A, okay? Let's just say that I'm trying to serialize this into some sort of final product array.
[00:01:29] So we'll just keep over here, this is going to be my final array. So the first thing I'm going to do is I'm going to dequeue this out of here. So the current node is going to be A. I'm going to process that, so I'm going to add it to the array, which I did over here, right?
[00:01:47] And then I'm going to enqueue both of its children. So after that it's going to look like B and C, right? Cuz these are the two children of A, right? You follow so far? So that's after one loop, one iteration, that's what it's gonna look like. I've added A, and now B and C are in the queue.
[00:02:13] So I'm dequeue the very next thing, which is gonna be off the front of the array. With the way that I've drawn this, right? So B, is going to come off, I'm going to add B here. And then I'm going to un-queue both of B's children, in this case it just has one child so its just gonna be one.
[00:02:36] So, its gonna be C, cuz C has still not been dequeued yet, right? And then I'm gonna add D.
>> Brian Holt: Right? Okay, so now I'm gonna dequeue C. I'm gonna add C over here.
>> Brian Holt: I'm gonna have D, here in the array, and then I'm gonna un-queue D's children, which D has no children.
[00:03:05] So It just finishes there, and that's what it looks like there. Okay? Now I'm gonna dequeue D.
>> Brian Holt: Sorry, I messed that up. C does have two children, so let's just, I think we'll just, there we go. It's like it never happened. It's like I didn't screw it up.
[00:03:33] Okay, so D, you had both the C's children, which are E and F.
>> Brian Holt: Right? Cuz that's what C's children are. And then afterwards, you dequeue D, which goes up here. Then you're gonna have E and F. D has no children so you don't have to do any dequeuing of that.
[00:03:59] Then we're going to dequeue E,
>> Brian Holt: E gets added up here. F is gonna move up, and E has the left child of G. So, it gets enqueued up there. And then we're gonna do F, put F up there
>> Brian Holt: And F has no children, so it's just G.
[00:04:27] And I'm gonna have G up there. G has no children, either. So at that point, the whole thing is done. How do we feel about that? Does that make more sense of how that's processing the whole thing?
>> Speaker 3: I think, I'm not sure if this is what the person online was wondering about.
[00:04:48] But the thing that kind of confuses me about why this works is that the first parameter of our function is Q. Which is, when it's an argument it is the trie. So how, does that make sense what I'm asking?
>> Brian Holt: Sure.
>> Speaker 3: How are those the same thing?
[00:05:12]
>> Brian Holt: So perhaps a better way of thinking about that, rather than thinking it as the whole trie, which this is a great question by the way. Rather than thinking about it as the whole trie, it's the root node.
>> Speaker 3: Okay, that's helpful.
>> Brian Holt: Yeah, that's tough to separate, because if you think about it more in the sense of B is a trie, and C is a trie, and F is a trie.
[00:05:35] Like they're all just little tries that make up bigger tries, right? It's a recursively defined trie, so A is just a node that makes up the trie and it just happens to be the whole trie.
>> Speaker 3: Okay.
>> Brian Holt: Is that more, better mental model?
>> Speaker 3: Yes.
>> Brian Holt: Okay, cool, that's a good question.
[00:05:54]
>> Brian Holt: Any other questions?
>> Brian Holt: Cool, you feel okay about that? Cool.
>> Brian Holt: Leave, cool. So that was Depth-first and Breadth-first Traversal. We saw Depth-first, which will get you as far away from the root note as possible. We saw Breadth-first, which will kind of keep you around the root note.