Description

We're going broad with breadth-first search! Well, actually, we're getting in line, or enqueuing ;) We walk through the steps of how breadth-first search (BFS) works, complete with holiday themed analogies and reindeers that need a GPS. We also compare and contrast the steps of BFS to those in DFS (depth-first search).

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Breaking Down Breadth-First Search from her basecs blog series.

Transcript

[00:00:00] SY: (Music) Welcome to the Basecs podcast, where we explore the basics of computer science concepts. I'm your host, Saron, founder of CodeNewbie.

[00:00:09] VJ: And I'm Vaidehi Joshi, author and developer.

[00:00:12] SY: And she is the brilliant mind behind the basecs blog series. Today we're talking about...

[00:00:17] VJ: Breadth-first search.

[00:00:19] SY: This season of the Basecs podcast is brought to you by our wonderful friends at Twilio. If you haven't checked out their API yet, you totally should. With Twilio, your app can send text messages and make phone calls with just five lines of code. And for a lot of developers, Twilio is the first API they've ever used. And that first time you type a few lines of code, run your program and see your phone light up with the text message? It's kind of magical. And as a thank you for being a podcast listener, you get a promo code for twenty dollars in free Twilio credit. Just text your name to 480-485-4321. You'll also get a link to a quick start guide for your favorite programming language. So text 480-485-4321. Link to that is in your show notes. Ok. Let's get started.

[00:01:09] SY: Ok, so last episode—actually I think it may have been over the course of two maybe three episodes—we've talked about depth-first search. Today, we're moving on to breadth-first search. What is breadth-first search?

[00:01:26] VJ: Well breadth-first search, which I'm going to try to just refer to it as BFS the...

[00:01:31] SY: Ok, thank you.

[00:01:31] VJ: ...rest of this episode because breadth and depth and. Oh.

[00:01:34] SY: It's just too much.

[00:01:34] VJ: It's like tongue spaghetti. So BFS is basically the opposite of DFS. And when I say the opposite what I mean is it's a completely different strategy when it comes to searching through a tree data structure. So a quick refresher, a tree has—well, a computer science tree grows from top to bottom, which is weird (Laughing) but it's fine. And there is a single root node and then, you know, that root node will have its own children nodes and it all kind of like grows and it could be deeper and deeper and deeper and have more nodes to it. So the two ways that we've kind of talked about approaching this is either going deep down one track, one branch of the tree or going wide and looking at one level of the tree at a time. And depth-first search is the first strategy where you kind of pursue one like little train of nodes all the way down until you have no more left. And breadth-first search is the one where you are just looking at one level at a time, and only when you've looked at that whole level, do you move down to the next level of nodes. So you're kind of systematically working your way down one section of the tree rather than going down and then back up and then down and then back up.

[00:02:55] SY: Ok. Ok, that makes a lot of sense, and I like that the names of the different searches pretty much say that. Like you could've guessed that that was the case even if you didn't really know how the algorithms themselves worked. When we were talking about depth-first search, DFS, we started with the root node. Where do we start with BFS?

[00:03:17] VJ: Luckily this is the one thing that these two strategies do have in common. With BFS, you also start at the root node.

[00:03:24] SY: Phew.

[00:03:24] VJ: Yeah.

[00:03:24] SY: One less thing to remember.

[00:03:26] VJ: Yeah.

[00:03:26] SY: Wonderful.

[00:03:27] VJ: It's great. It's great when that works out. And part of the reason for that is because that is the only thing you can start with because when you have a tree structure, its nodes. And the first thing...

[00:03:37] SY: Yeah.

[00:03:37] VJ: ...you usually can deal with with a tree structure is the root node. That's all you have.

[00:03:41] SY: That's true.

[00:03:42] VJ: You kind of have to start there.

[00:03:42] SY: I didn't think of it like that. Wait so in general if you're doing some type of algorithm thingy with the tree, do you generally start at the root node?

[00:03:52] VJ: Yeah. Yeah, and usually when you...

[00:03:54] SY: Ok.

[00:03:55] VJ: ...have like implementations of a tree, a lot of people will—like you can implement a tree different ways depending on the language and, you know, the way that you're kind of thinking about it. But usually, you'll have a either a tree object or your tree object just contains one node to begin with, and that is a root node. And then that root node has its references. And so you basically are only starting with the one node to begin with.

[00:04:20] SY: Yeah.

[00:04:20] VJ: And that is kind of encapsulating the entry point into the tree structure.

[00:04:26] SY: Oh wonderful. Ok. So I may not know what I'm doing, but I know where to start.

[00:04:29] VJ: Your instincts are totally right.

[00:04:31] SY: That’s good. Nice. Ok. So when we were doing depth-first search, there were a lot of, there were a lot of different ways and we had like pre-order and post order and a, and a bunch of different ways that we could do it. But regardless of what order we picked, it was generally the same idea of I read something, I look, I look, and then I read something and then I look, I look, you know. This kind of like those three general steps that made a process. Is that similar to how breadth-first search works?

[00:05:05] VJ: Well you do have similar steps in that you're still dealing with nodes, right? And so ultimately you are gonna wanna read them, and you are gonna wanna like look at the children nodes in some capacity. But the three things that we are going to really concern ourselves with in terms of breadth-first search, BFS, is reading the data of the node but then also making note of what its children nodes are and then reading the values that. That is similar in that you are doing the same things, but the way that we're gonna do it is gonna be a little bit different because we can't just go all the way down the branch of a tree. We need to like have a little bit more order in terms of, you know, we only wanna look at one level first. And the, the logic of how do I only look at one level...

[00:05:58] SY: Right.

[00:05:58] VJ: ...that's a little bit interesting here.

[00:06:00] SY: Yeah, because when we talk about going deep, going all the way down, intuitively it makes a lot of sense because they're all connected, right? Like I'm just, I'm literally just following the path of the branches all the way until I reach the end, right? And I can't really go any more. But when we're talking about levels just visually going across a tree, there's not really a path that goes across. You, you kind of have to like jump nodes or something, right?

[00:06:27] VJ: Yeah and, yeah. And like if you think about it like if you imagine the simplest tree—it's like a root node with two children—those two children don't have any real way of knowing about each other, right? There's no...

[00:06:40] SY: It's true. They have to go back up.

[00:06:40] VJ: ...reference. Exactly. Yeah.

[00:06:43] SY: Yeah.

[00:06:43] VJ: There, there's—they don't know about each other. They're not like holding hands with a little link or...

[00:06:47] SY: Right.

[00:06:48] VJ: ...edge or anything. It's just the root node or, you know, if it, if we're talking about a big tree with many, many parents, it's always just the parent node that has, you know that...

[00:06:57] SY: Connection.

[00:06:58] VJ: ...connection to the children.

[00:07:00] SY: Yeah.

[00:07:00] VJ: So that, that makes it a little tricky, but there is a, there is a way to solve it.

[00:07:04] SY: Ok, ok. So let's, let's start. Let's start at the very top. Let's start with our root. What is the first thing that I do with my root node if I'm doing breadth-first search?

[00:07:16] VJ: So the first thing when you enter into a tree and you want to run BFS on it, the first thing you're probably gonna wanna do is check the root node 'cause...

[00:07:24] SY: Ok.

[00:07:24] VJ: ...that is what you have. And if you think about it level by level, the first level...

[00:07:28] SY: Right.

[00:07:29] VJ: ...is the root node.

[00:07:29] SY: Yeah.

[00:07:30] VJ: There's nothing else that, you know...

[00:07:32] SY: It's got a whole level to itself. It's got the penthouse. (Laughing)

[00:07:36] VJ: Exactly. And there you go. Step one is done. Level one is checked.

[00:07:39] SY: Nailed it.

[00:07:39] VJ: You know? That's with one node. But it's gonna get more complicated as you go on 'cause there will be more nodes per level. And then you'll be wondering why did I make my tree so big? (Laughing)

[00:07:48] SY: Such a big apartment building. Ok, so I, I finished my first level, finished my root level. Everything's good. Can I tell you what I wanna do, and can you tell me how it's probably wrong?

[00:08:03] VJ: Yes. Tell me what you wanna do.

[00:08:04] SY: Ok, so first I'm done with that level. I wanna go down a level. And we talked last episode, a couple episodes ago how we generally like to go from left to right for some reason. So I just instinctively wanna go to my left node, my left child node first. So that's what I wanna do. I wanna go to my left child node.

[00:08:24] VJ: Ok. Cool.

[00:08:26] SY: Is that, is that ok?

[00:08:26] VJ: Yeah, that's fine. Now we're there.

[00:08:28] SY: Ok, so now were there. Ok, now what do we do? Ok. So what I want to do is I wanna, I wanna like see what's up with the left child nodes. I wanna, I wanna read it. I wanna, I wanna ask it what it is.

[00:08:41] VJ: Yeah. What's your deal, left child?

[00:08:42] SY: What's your deal? Yeah. Can I do that?

[00:08:44] VJ: Yeah. You can read it.

[00:08:45] SY: Ok. Ok. I read it. So now I have two values. I have my root node, and then I went down. Now I have my left child node value. Ok, so now we talked about breadth, so I need to go across the level. So stay at...

[00:08:59] VJ: Yeah.

[00:08:59] SY: ...the same level. So I wanna get to the right child. Ok, so now the problem is I don't have a direct connection to that right child. So the only way I can really get there is to go back up. Can I, can I go back up?

[00:09:15] VJ: Well I hate to break it to you, but there is no way to go back up because...

[00:09:19] SY: Why?

[00:09:19] VJ: ...the—because the link... I'm sorry. (Laughing)

[00:09:24] SY: That's not fair.

[00:09:24] VJ: You seem so disappointed.

[00:09:27] SY: I had a plan.

[00:09:30] VJ: Well the way that the, the way that the tree structure is built is that only the parent node knows about the children. These are like one-way links.

[00:09:38] SY: Oh my god. It has like a secret sibling? Like it's like the brother I never knew I had?

[00:09:43] VJ: Well, yeah. You don't—yeah. Exactly. You don't know.

[00:09:44] SY: Drama.

[00:09:45] VJ: But your parent knows. And you cannot go back to your parent. You have to kind of like—if you wanna find out who the sibling is, you have to start the root node. You can go down to the child, but the child doesn't know about the other sibling because the only person who knows...

[00:10:00] SY: And I can't go back up and ask mom like, "what's up? Like ma..." Like I can't...

[00:10:05] VJ: Yeah.

[00:10:05] SY: ...go back up to mom. I'm too scared of her.

[00:10:06] VJ: Yeah.

[00:10:07] SY: It just doesn't work.

[00:10:07] VJ: Well yeah. You can't, you can't—it's a one-way communication...

[00:10:08] SY: Wow.

[00:10:09] VJ: ...in this parent-child relationship.

[00:10:12] SY: Damn. That's a, that's a tough childhood.

[00:10:12] VJ: She does the talking. You don't talk back. (Laughing) You do not talk back.

[00:10:17] SY: No talk... She just gives you commands.

[00:10:19] VJ: No sassing.

[00:10:20] SY: No sass. How dare you sass me? Inquiring about possible family members. Who do you think you are? Go to your room.

[00:10:29] VJ: You wanna know if you have a sibling?

[00:10:33] SY: Too far.

[00:10:33] VJ: Ludicrous.

[00:10:34] SY: Ludicrous. Oh my goodness. Oh, such an interesting Christmas it's going to be. (Laughing) Ok. So I, I have no mechanism. I have no way of asking my parent if I have any siblings. So, so I guess I'm, I guess I'm kinda stuck. Like there's nothing, nothing I can do. Oh man...

[00:10:59] VJ: Yeah, well.

[00:10:59] SY: ...what do I do?

[00:11:01] VJ: Well the, the big problem—and this is what you kind of were hinting at before—is what you've realized is that there are no reverse links, right?

[00:11:09] SY: Yeah.

[00:11:10] VJ: There's, there's only one-directional links. You can't link back up to the parent because children don't have references or pointers to their parents. Only parents have them for their children. So what we need to do is we need to kind of be a little clever and figure out how to, you know, mentally note to ourselves "hey, we wanna check these nodes in this order. We wanna check all the children first of this node." But we don't wanna actually go and travel there and read the data immediately because the moment we do that...

[00:11:42] SY: We can't go... back

[00:11:42] VJ: Well now we've lost reference to any of our siblings.

[00:11:45] SY: Yeah.

[00:11:45] VJ: So we kind of have to start at the root node, which is the top level.

[00:11:49] SY: Starting over.

[00:11:50] VJ: And yeah. We'll start over, and we'll—it's fine to read that first 'cause...

[00:11:54] SY: Ok.

[00:11:54] VJ: ...you still wanna do that no matter what 'cause you do wanna read the data. That's the first thing you're working with. But what you need to do is you kind of need to ask the root node, "who are your children nodes?" And we're gonna decide whichever order we're gonna read them in. So let's say we're gonna go left to right. We'll read the left child first and the right child, right? We're gonna do it in that order. So we're gonna ask the root node. We're not gonna travel anywhere. We're gonna ask the root node, "who are your children nodes?" And we're gonna kind of write down a list of them. We're going to keep references to them.

[00:12:21] SY: OK.

[00:12:21] VJ: Like just a little—you can imagine like we had a little notepad and we're like "hey. Tell us about your kids."

[00:12:25] SY: Yeah.

[00:12:26] VJ: "We're gonna write their names down. We'll go, we'll go to their houses later. But right now just tell me your kids and where they live." (Laughing)

[00:12:32] SY: Smart. Smart. Ok. Ok, so when we talk about references to the children is that kind of like writing down their address?

[00:12:44] VJ: Yes. Yeah. You can kind of think of that and like literally when you're talking about a reference to children nodes, what a lot of the times people are referring to is their place in memory and...

[00:12:57] SY: Ok.

[00:12:57] VJ: ...depending on the language that you use, you probably aren't even thinking about memory sometimes. What you're really just thinking about is like, you know, you might—if you're thinking about it in code, you might be thinking like node.left, node.right. Like just get me the object or give me the, you know, give me the node whatever that looks like. But really, what you're usually doing is you're pointing to a place in memory, and you're saying "hey, go retrieve whatever is in that place in memory."

[00:13:21] SY: Ok.

[00:13:22] VJ: You can think of it as like, you know, this parent had two kids and they moved away, and now they have their own houses.

[00:13:27] SY: Yeah.

[00:13:27] VJ: And so you're kind of going to their house and you're saying, "I'm gonna go visit your kids. Can you tell me—you, you know your kids. You're the parent. Tell us where they live."

[00:13:37] SY: Yeah.

[00:13:37] VJ: I'm gonna write down their address, and then I'm gonna go visit them in the order that I want later. And now I know where they are.

[00:13:43] SY: Oh.

[00:13:43] VJ: So now even if I go visit one child, I don't need to freak out about not knowing where the sibling is 'cause I went and got that information already.

[00:13:51] SY: Yeah. I got their address. I know where they live.

[00:13:53] VJ: Exactly.

[00:13:54] SY: So no stopping me... in a friendly way, not like in a killer stalker way.

[00:13:58] VJ: Yeah. No, no. Not in a serial killer kinda way. This is like a, you know, completely innocent...

[00:14:04] SY: Yes. I wanna get them presents for Christmas.

[00:14:05] VJ: Not at all scary.

[00:14:05] SY: That's all it is. That's all.

[00:14:07] VJ: I know. I, I kinda wish I hadn't gone with the "go ask people for their children's addresses" metaphor (Laughing) 'cause now I'm like oh that could be weird.

[00:14:14] SY: Oh my God. No, no, no. You're Santa Claus. You're Santa Claus.

[00:14:18] VJ: Oh.

[00:14:19] SY: You get it? Like you're San—and you're like, "what, what do you want for..." No, Santa Claus is magical. He already knows where all the addresses are. He doesn't need to talk to...

[00:14:25] VJ: Can I have reindeer though? I like the idea of that.

[00:14:28] SY: Ok. I'm fine with that. The reindeer doesn't know. The reindeer needs the addresses to put in their...

[00:14:32] VJ: Yeah. That seems, that seems seems more ok.

[00:14:34] SY: Into their GPS. Yes. Yes. That’s makes a lotta...this is all coming together. We will make this work. Dammit.

[00:14:42] VJ: We are totally recording this in the middle of summer, which (Laughing) is why it's great that we have, gonna have all these holiday references.

[00:14:46] SY: The timing of this is terrible. Ok. Ok, cool. So, so I'm, I'm trying to compare and contrast this, this breadth-first search process to the depth-first search process that we already learned, and it sounds like one really big difference here is that we have a new tool. We have our little list, our little list of addresses for the children nodes that we're not using yet, but we know we can use for later. And we didn't have that with depth-first search.

[00:15:17] VJ: Right. Yeah. We didn't, we didn't even need to...

[00:15:19] SY: Right.

[00:15:20] VJ: ...because we kind of—it's almost like with depth-first search that, you know, they live on a street or in a cul-de-sac or something. And the parent can tell you, "oh, just go next door."

[00:15:28] SY: Right.

[00:15:28] VJ: Go next door to the child.

[00:15:29] SY: Yeah.

[00:15:29] VJ: Go next door to the next child. And, you know, you kind of just keep going down 'till you get to the last house. And then you just work your way back up. And then you kind of like, you can imagine like all these streets that are connecting from this one root node. Whereas with breadth-first search, it's not that easy. You can't just go next door. You can't just keep going down...

[00:15:47] SY: Right.

[00:15:47] VJ: ...the street because now you kind of have to go from one side of the neighborhood to the other. Because the two children, the two levels, they don't know about each other. You can't just have a direct connection, which is why you need to kind of keep that list. You need to keep the reference, you know, to keep note of who the children nodes are so that when you wanna visit them in order, you can.

[00:16:12] SY: Ok. So this list... what is that in computer science-y land? It sounds important. I feel like it has a name. What, what is it?

[00:16:21] VJ: It does. Oh my gosh. This is my favorite thing when this happens. So this list that seems super helpful—it's actually something we have run into. I'm pretty sure we ran into it in season one.

[00:16:31] SY: Ok.

[00:16:32] VJ: Maybe it was season two. I don't know. The seasons all blur together, and we're talking about Christmas in August. Who knows? (Laughing) But this list that we're really, you know, referring to is a Queue data structure.

[00:16:45] SY: Oh, we did talk about queues.

[00:16:47] VJ: I know. I remember how fun that was. Queues are good.

[00:16:50] SY: Yeah.

[00:16:52] VJ: Love me some good queues. (Laughing) So since it's been a while. Quick refresher.

[00:16:57] SY: Yeah.

[00:16:57] VJ: A queue is a data structure. It's actually a data type, an abstract data type, but the important bit about a queue is that it's linear so there's a sense of order. And we've been talking about like trees for quite a while now. You know, we've talking about algorithms for tree traversal. So we haven't been talking about linear data structures, really. But this is a linear data structure that's actually gonna come in handy for us now as we write an algorithm to help traverse through a non-linear data structure like a tree. And the one important bit to know about queues is that they can grow and shrink in size, and the way that you kind of deal with them is that you enqueue items to them. And then you dequeue items to them. And queues operate according to a first-in, first-out principle. So the first thing that I enqueue is the first thing I'm gonna pull off and process. So it's, it's kinda like standing in a line, you know, at the DMV or, you know, at a sandwich...

[00:17:57] SY: Yeah.

[00:17:57] VJ: ...shop or something. Like whoever gets there first is the first one that's gonna be served. And that's the linear aspect of the queue data structure. That's exactly what our list is.

[00:18:05] SY: Very cool. Ok, so for this queue, we are putting addresses, references to our, to the nodes that are on the same level. And then what do we do?

[00:18:25] VJ: Well the problem we were trying to get around before was once we go to a child node, there is no way for us to figure out where its sibling lives...

[00:18:32] SY: Yes.

[00:18:32] VJ: ...'cause it doesn't have the address...

[00:18:36] SY: yes.

[00:18:36] VJ: ...right? So now what we're doing is we are getting those addresses, those references ahead of time. So now we can kind of proceed with what you wanted to do before, which is we can now go to the next level. So imagine that we started at the root node.

[00:18:50] SY: Yeah.

[00:18:50] VJ: And we visited it, and then we collected the information about its children nodes. We're more well equipped to go to the child node and be like, "all right. Tell me your story. And now when I leave your house, I actually know where your sibling lives already 'cause I wrote it down."

[00:19:06] SY: So I'm good. Yeah.

[00:19:07] VJ: Yeah. And this is—like if we're gonna talk about it in a more technical sense—I'm using this like metaphor of addresses, but really what we're doing is when we go to the root node, we're reading the data. We're, you know, asking the root node whatever its value is, and then we're saying, "tell us who your children are. Tell us, you know, what their addresses are." Or, in other words, when you tell us what your left node and right node is, we're gonna enqueue them into our queue. We're gonna add them to our list. And then we're gonna work our way through that list because that list is telling us, "oh, these are your children, and these are the nodes we need to visit in order."

[00:19:45] SY: Right.

[00:19:46] VJ: And we're kind of gonna repeat that same step. We'll read a node's data. We'll enqueue its children, and then we'll just move on to the next node in that queue.

[00:19:56] SY: Oh, ok, ok, ok. Can we, can we go through one? Can we go through an example?

[00:19:57] VJ: Yeah.

[00:19:58] SY: Ok, ok, ok.

[00:19:58] VJ: Totally.

[00:20:01] SY: So we start with the root. We read the root. And then before we leave, we say "tell me the reference for your left child node and your right child node." We add each of these to our queue. So earlier when we talked about how DFS is like a read and then look-look, this is kind of like a, a read and then an add-add 'cause I'm adding to the queue.

[00:20:27] VJ: Yep.

[00:20:27] SY: And then once I've added all that information, now I'm ready to go down a level. So I start with my left child node. And I'm there...

[00:20:37] VJ: yep.

[00:20:37] SY: And I want to read it. Can I—I can read it now because I know where the right child's address is.

[00:20:43] VJ: Yeah. And you—honestly, once you've enqueued things...

[00:20:44] SY: Yeah.

[00:20:44] VJ: ...you don't even need to worry about left child right child of anything else.

[00:20:51] SY: Oh. I'm just going in the queue. I'm just using the queue...

[00:20:53] VJ: Exactly.

[00:20:54] SY: ...to tell me what to do next. Oh, alright.

[00:20:54] VJ: Yeah. You're looking at the queue and you're...

[00:20:57] SY: Ok, queue.

[00:20:57] VJ: ...just saying, "ok, I have a node. Do I have a node to look at? Yeah. I have a node to look at. Ok. Does it have a left and a right? Stick them at the end of the queue. And then removed the thing I was just reading and move on to the next thing."

[00:21:09] SY: Ok. Got it. Ok. So add my root, read my root, added my left child, my right child. Now in my queue I have—oh I have a burp. (Laughing) So in my queue now I have the two nodes, which happen to be the left child and right child. So then the left child, I read it. And now that I've read it—ok, it, it has children. So I wanna like dequeue it. Is that the word?

[00:21:44] VJ: Well before you dequeue it...

[00:21:46] SY: Before I dequeue it, I have to, I have to add the children.

[00:21:48] VJ: Yeah.

[00:21:48] SY: Ok.

[00:21:49] VJ: Before you remove—like part of the process of handling a node in the queue is you're gonna read its value, and you're gonna say, "do you have children? If you do, I'm gonna stick your children..." (Laughing) Well, ok, this sounds bad. "I'm gonna stick your children's address to the end of my queue." Oh... I promise nothing—none of this is supposed to be about kidnapping young children. Let's go back to the reindeer. What if Rudolph is involved?

[00:22:22] SY: Before we can give you your present, we have to give presents to your children. And for that, we need their addresses. That's all. And we're gonna add them to Santa's list.

[00:22:32] VJ: Yeah. I should've really gone with the Santa's list metaphor. I keep forgetting.

[00:22:36] SY: That's ok. That's fine. That's what I'm here for.

[00:22:39] VJ: But I guess the important bit in that is that part of processing a node is reading. But then also before you can say...

[00:22:47] SY: Yeah.

[00:22:47] VJ: ..."oh I'm done with it," you gotta know who its children are because when you get down to the next level, you will miss the addresses for that, for those...

[00:22:55] SY: Right.

[00:22:55] VJ: ...nodes at that level. So before you can, you know, kind of dequeue the node, you have to be like, "ok, I've read you and I've added your children. All right. Nothing left to do." Get out of the queue.

[00:23:04] SY: Got it.

[00:23:05] VJ: And then you go, just go to the next node in the queue, which the next node in the queue once you're done with the whole level will be the beginning of the next level.

[00:23:13] SY: Oh. Ok, ok, ok. So originally we had root node, added the left child, added the right child. So now in my queue I have my left child, then my right child. Now I can go to my left child with full confidence. I read my left child, and then I say, "ok, where are your children?" And then I add their addresses to my queue...

[00:23:35] VJ: The end of the queue. Yeah.

[00:23:36] SY: To the end of the queue. And then after doing that, I'm now done with my original left child node, and I pop that off. So now what's left in my queue is the first right child node because we haven't actually gone there yet. But I also have the left child's two children's addresses.

[00:23:58] VJ: Right. So what you have right now is the end of one level...

[00:24:01] SY: Yeah. In the beginning of the...ok....

[00:24:05] VJ: And the beginning of the next.

[00:24:05] SY: Neat. Ok. And then when I process, the, the next thing in my queue that, that's the right child node. And I'm gonna read it, and then I'm gonna say "do you have children? If so, what are their addresses?" And then I enqueue those two addresses to the end of my queue.

[00:24:26] VJ: And what's in the queue now?

[00:24:27] SY: So now, now that I'm done with my right child node, I can dequeue it. So now what's left in my queue is all the addresses for the third level, the next level...

[00:24:39] VJ: Right.

[00:24:39] SY: ...entirely.

[00:24:40] VJ: Yeah.

[00:24:40] SY: Oh snap.

[00:24:41] VJ: And it'll be completely in order, too.

[00:24:43] SY: Yeah.

[00:24:43] VJ: It'll be in order the left...

[00:24:46] SY: It just goes left to right.

[00:24:47] VJ: ...child. Yeah, yeah. You're reading it...

[00:24:49] SY: Very cool.

[00:24:49] VJ: ...in order. It'll be the left child's left child; then the left child's right child; then the right child's left (Laughing) child; and the right child's right child. But basically if you imagine a tree, you're basically kind of like scanning. You're like...

[00:25:01] SY: Yeah.

[00:25:02] VJ: ...top node. Now next level. Read those. Now the next level from left to right. Read those.

[00:25:08] SY: Yep.

[00:25:08] VJ: And it's almost just because you have this set of, you know, set of steps that you're following for every single node. It ends up kind of just falling into place.

[00:25:17] SY: Yeah.

[00:25:17] VJ: And that's the beauty of this algorithm is it just works out...

[00:25:19] SY: Very cool.

[00:25:19] VJ: ...that way. And you're not even having that do the mental, you know, gymnastics of thinking about it. All you're doing is just enqueuing things.

[00:25:25] SY: Adding and popping. Adding and popping. (Laughing) Very cool. Ok. So we walked through a, a pretty high-level (Music) example of, you know, just calling things left and right, but I think this algorithm is really gonna shine when we go through an actual tree with real numbers and stuff. So next episode we're gonna walk through an example of breadth-first search very, very slowly so you can hear exactly how it works with real numbers. But for today, I think that's the end of the show. If you liked what you heard, please leave us a review. Make sure to check out Vaidehi's blog post. Link to that is in your show notes. Also wanna give a huge shout out to Twilio for sponsoring the season. Make sure to check out their awesome API. To get your twenty dollars in free Twilio credit, text your name 480-485-4321. Phone number and link are in your show notes. Vaidehi, you wanna say good-bye?

[00:26:17] VJ: Bye, everyone.

[00:26:18] SY: Thanks for listening. See you next week.

[00:26:22] SY: Why do we say doing? Doing…

[00:26:24] VJ: We're covering? We're talking about...

[00:26:25] SY: ...talking about. Yeah. That was weird. (Laughing) It's like doing... what the hell? It's not a project. Ok.