Description

We dive into depth-first-search by exploring our first of three strategies: preorder! Let's walk through an example step-by-step and get to know members of Saron's fictitious tree family along the way.

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Demystifying Depth-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:11] SY: And she is the brilliant mind behind the basecs blog series. Today we're continuing our conversation about...

[00:00:18] VJ: Depth-first search, or DFS.

[00:00:20] 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's first time you type a few lines of code, run your program and see your phone write 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:10] SY: D-F-S. Ok. So let's do a really quick overview of what depth-first search is.

[00:01:18] VJ: Sure. So depth-first search is—in the context of trees, when you start going down a path, down a branch of a tree, if you will, you are not going to stop searching through it until you get to the end, which basically means you're going to keep on searching deep into the tree and to one branch of the tree until you get to a leaf, which as you'll recall, is like the last node on a path that doesn't have any children. So in depth-first search regardless of, you know, what different types of strategies you might use, any type of depth-first search is always going to search down the branch of a tree until it gets to a leave, and then it's gonna work its way back to the center, or the root node or the trunk of the tree after going deep.

[00:02:07] SY: And for our purposes, this tree is upside down...

[00:02:10] VJ: Right.

[00:02:10] SY: And the branches are pointing... (Laughing)

[00:02:12] VJ: I feel like...

[00:02:12] SY: Just to clarify.

[00:02:13] VJ: That's a thing most people would be like, you know, mention early and we're just so into it now that we're like, "oh, right." We should maybe clarify.

[00:02:20] SY: We all know how, how trees work. Trunks are at the top, as always. Per usj. Yeah, so this is an upside-down tree, and we're starting at branches, which are all the way, all the way down. And we are kind of like climbing our way back up in a sense versus breadth-first search, which I hate saying, which we haven't talked about but is kind of the opposite idea of going wide instead of going deep. Short version. And we'll get into that in a different episode. Ok. So one thing that we talked about which I thought was really interesting is that there are—well they're actually a total of six strategies. We're gonna focus on three of the six strategies. They're called pre-order, in order, post-order—all orders. And they are called pre-, in and post- because they all have to do with—drumroll please—the order; the order of something. What order are we referring to?

[00:03:15] VJ: I mean, as much as I love trees, there's really not that much you can do when you're in, you're in, you know, searching through a tree because in the context of a binary search tree, which is what we're, you know, kind of confining ourselves with today with DFS, every single node in a tree has like some data. And then the only other thing it really has is a reference to a left node if it has one and a right node if it has one. So the only thing you can really do when you're searching through the nodes of a tree are like look at its value, the value that it contains, whatever data it has and then go look at its left child and its right child. And that's pretty much it. Those are the three things. So...

[00:03:56] SY: You make it sounds so easy. I love it. (Laughing) You make it sound just—I swear before talking to you, before doing this whole podcast, I thought trees were this terrible, scary thing. You're just like whatcha gonna do with a tree? You got (Laughing) two things you could do with a tree. You can, you can read what, what it, it has—it's data—or you can look at its children. Like that just sounds like, like a family barbecue. That's great. That's awesome.

[00:04:20] VJ: I love that. Family barbecue.

[00:04:22] SY: Family barbecue of trees. Oh, that's probably not a good idea. (Laughing) Ok. So there are two things we can do: look at the children and read ourselves, I guess. So order... What does it have to do with order?

[00:04:37] VJ: Well if you can only do three things—look at the left child, look at the right child and read your data—well the order that you do those things, there's basically like as you mentioned, six strategies. And guess what, those six strategies are the six different permutations that you can pretty much do those three things in. So, for example, you could start with a strategy and be like, "I'm gonna search through this tree. And every time I search, I'm gonna read my value. And then I'm gonna look at my left child. And then I'm gonna look at my right child." Or you could be like, "no, no, no, no, no. I'm always gonna look at the left child. Then I'm gonna read myself and then I'm gonna go look at my right child." Or you could be like extremely like selfless parent and be like, "no, no I'm gonna look at my left child—make sure it's ok—then my right child (Laughing) and then I'm gonna put myself last."

[00:05:27] SY: Aw. Sacrificing parent.

[00:05:31] VJ: Yeah. No, me neither.

[00:05:32] SY: Be like look at me, kay? I'm the star. I made these. That's what...

[00:05:36] VJ: You children follow behind me.

[00:05:37] SY: Yeah.

[00:05:38] VJ: If you're there, you're there. You might not be there. I don't really care.

[00:05:40] SY: Clearly we don't have kids. (Laughing) Every parent's like what the hell? Ok. So, so these three things and the order, they don't really sound like a big deal. Like why, why does it matter if I look at my left kid first then tell you what I got then look at my right kid. Like why, why do those three things matter? They seem really arbitrary.

[00:06:07] VJ: Well I think this might be an easier thing to see if you, you know, can walk through an example, which we'll do soon. But you'll have to trust me for now. Just have a little faith here.

[00:06:16] SY: Ok.

[00:06:17] VJ: The different strategies will give you different results because at you might imagine, if you're going and looking at your children first and looking at yourself last, then if you're searching through a tree, you're always gonna search through the children of the node that you're looking at instead of yourself. But if you're looking at yourself first, then the way that you're gonna search through and evaluate the values—let's say you're doing something as simple as just like I'm gonna just print out whatever my value is. Even if you're just printing it out, the order that things will get printed out in will be slightly different depending on what strategy you use.

[00:06:50] SY: Ok. I guess I'll just have to believe you. I'll have to believe you, but I'm just saying I'm a little skeptical for now 'cause it seems like not a big deal, but we'll see, we'll see, we'll see what we, we'll see what we get at the end. Ok so let's walk through an example of what it looks like to implement the pre-order strategy and how that works. Ok, so this is gonna be, this is gonna be a little hard 'cause this is a more visual thing, but we're gonna do our best here. Ok so let's look at the first strategy pre-order. Now what does pre-order mean. What are—what order are we doing those three things you mentioned?

[00:07:29] VJ: So for brevity's sake, I'm gonna just kind of take those three things and just give them a little short name, like short form. So let's say when I am reading my own value, we're just gonna call that reading my own data. So we'll just say that's "D," doing "D" first. And if I'm looking at my left child, I'm looking at "L," my left child. And we'll just say that's "L." And if I'm doing the step of looking at my right child, I'm gonna call that step "R." So there's "D" and then there's "L" and then there's "R." And remember...

[00:07:59] SY: Ok.

[00:08:00] VJ: ...those are the three things. So we could do LDR. We could do LRD. We could do DLR. We could do three other options that I'm not even gonna talk about. But pre-order—and the name kind of helps you a little bit—pre-order means I'm going to look at myself and then I'm going to look at my left child and my right child. So in other words, it's a DLR format.

[00:08:22] SY: Ok.

[00:08:23] VJ: I'm going to read my own data, "D," then I'm gonna look at the data of "L" and then I'm gonna look at "R": DLR.

[00:08:29] SY: Ok. And just to clarify—when I'm looking to my left, am I actually reading the data also at my left? Or what, what am I looking for? What am I doing there?

[00:08:43] VJ: You're looking to see if you have a left.

[00:08:45] SY: Ah, ok.

[00:08:46] VJ: And if you have a left, then you're going to do the exact same steps.

[00:08:50] SY: Oh.

[00:08:51] VJ: So this is like where the algorithmic aspect of DFS really comes into play. So last episode, we talked about how algorithms are like instructions of what you're supposed to do. So DLR itself is the algorithm, is part of the algorithm because you're basically saying, "no matter what I'm always, I'm always going to read my data then do my left and my right." And I'm gonna do the same steps again and again for every node that I look at.

[00:09:16] SY: Interesting. Ok so in other words, if we do for DLR, if I'm, I'm the mama, I'm the root, I read myself first, then—I just did my "D"—now I do the "L," which is looking to see if I have a left child. And then if I do have a left child, then now that left child becomes parent, the, the, the new root in a sense?

[00:09:46] VJ: That becomes the new parent. Yeah. That's totally right.

[00:09:49] SY: That becomes the new parent. Ok so then that child would have to go ok now do I have—no, no, no, no. Dammit I messed it up again. Now that left child is the, the new parent. So if I do DLR, if I basically restarted my, my algorithm, so I start back at my "D," which is that child is now reading itself. So we print that out and now my child is gonna say, "ok, now do I have a left?" And then...

[00:10:20] VJ: Yep.

[00:10:20] SY: ...if they do—oh God, I'm a grandmother. If they do, (Laughing) then now...

[00:10:28] VJ: It happened in one episode. You just didn't even know. That's what they say about time. You blink and then it just goes by.

[00:10:35] SY: It's like the same about podcasting.

[00:10:35] VJ: Or in our case, you pre-order through a tree. (Laughing)

[00:10:40] SY: My mom will be thrilled. So now like my grandchild is now the new parent in the situation, and then that grandchild is reading itself 'cause we're back at "D." And then they're gonna say, "ok do I have a left." I hope they don't have a left child 'cause that would make me a great-grandmother. (Laughing) So they are, are basically ok cool, I don't have a left. Now they're gonna check their, their right child 'cause that's the "R" part of DLR. And they're gonna not have a right child either. So now they're kind of, they're kinda done.

[00:11:16] VJ: Yep.

[00:11:17] SY: Right?

[00:11:17] VJ: They're done. They're done, but you know who's not done?

[00:11:19] SY: Who's not done?

[00:11:20] VJ: Their parent.

[00:11:20] SY: Oh. Oh right 'cause we kinda stopped at the left child part of things.

[00:11:25] VJ: Yeah, so because it's DLR, we basically started with one node, and we printed it out. And then we just went, kept going down and did all these "L's," printed like the parent node and then only looked at the left children. And all these right children are like hey, what about me? (Laughing) Just 'cause I'm second doesn't mean I shouldn't be loved. So, so now we've resolved the left for this last generation of parents kind of, but we didn't resolve the right. So now we've done the "D." We've done the "L," but now we need to do the "R" so that we can resolve that node that we were looking at.

[00:12:01] SY: Ok. So do re—quick recap. I'm the parent. We went to my left child. That left child went to its left child. That child has no left or rights. That's done, but now my child has just resolved its left child situation. And now it needs to go over to its right. Ok so it goes over to its right child. Let's say it has one. Now my other grandchild needs to print out itself 'cause now we're restarting. We're back at "D." It prints out itself. Then it says, "ok, do I have a left? No I don't. Do I have a right? No I don't." Ok, now I'm done. Now I kick it back up to...

[00:12:46] VJ: Its parent.

[00:12:46] SY: ...its parent. Yep.

[00:12:47] VJ: Yep.

[00:12:48] SY: Which is my child. So now from my child's perspective, I already finished resolving the left child part of things. Now I just finished resolving the right child side of things. So not it's gonna report back to me and say, "hey, I'm done."

[00:13:05] VJ: Yeah. So basically what's kinda cool is you just went to one of your children and you said go down to your whole like...

[00:13:12] SY: Your whole family.

[00:13:12] VJ: Your whole hierarchy. Your whole, all of your descendants. Print yourselves out in this order, and then come back to me. But you have more than one child.

[00:13:23] SY: Oh God.

[00:13:23] VJ: You have a left child and a right child.

[00:13:24] SY: So many babies. (Laughing) Ok so I just did all of that just to one child, my left child, but I still—you're right, I still have my right child, who I haven't, I haven't even talked to. Oh my God. How many minutes has it been? So now I say to my right child, ok right child, it's, you know, it's, it's your turn to shine. Right child says yes, mama. (Laughing) And...

[00:13:48] VJ: They're so good. So obedient.

[00:13:50] SY: Very well behaved. Well-behaved children.

[00:13:52] VJ: It's not even complaining that it's second here. That's what I'm surprised about.

[00:13:54] SY: No, it's like I know my place. I'm like yeah, you do. So is (Laughing) that—I'm gonna be a great mom—is that child, does that child have children?

[00:14:04] VJ: Yeah, it just has two children.

[00:14:05] SY: It has two children. Ok.

[00:14:06 VJ: I just made this up arbitrarily.

[00:14:07] SY: That's...

[00:14:08] VJ: This is great. I have so much power over your...

[00:14:10] SY: I know. (Laughing)

[00:14:12] VJ: Your...

[00:14:12] SY: I was just thinking, you have a lot of say in my reproductive decisions.

[00:14:17] VJ: Yeah. (Laughing)

[00:14:17] SY: Ok so, so—ok, so I have my right child and I say, "hey, child, it's your turn." Now right child says, "ok cool." Now that I've handed it off to the right child, we're starting the DLR process again. So it's going to do the "D," which means it's gonna print itself. Then it's gonna say, "ok, do I have a left child? Yes I do." Ok, now we've passed the baton onto that left child.

[00:14:46] VJ: Oh I like the "pass the baton."

[00:14:48] SY: You like the baton? Yeah.

[00:14:49] VJ: It's like—that's great. It's like because you can only—in this family, this tree, only one person can speak at once...

[00:14:56] SY: Yeah.

[00:14:56] VJ: ...which means you can only be looking at one node at once, which is the baton. That's great.

[00:15:00] SY: Yeah.

[00:15:01] Think about all the family barbecues that'd be so much more organized if there was only...

[00:15:04] SY: You know...

[00:15:05] VJ: ...like one baton.

[00:15:05] SY: You know? You'd have the chicken done on time.

[00:15:06] VJ: You wouldn't talk over each other. Oh, that, too.

[00:15:08] SY: The hot dogs done on time. I love how you're thinking about like communication and, you know, relationship building, and I'm just thinking about food. (Laughing) It's great.

[00:15:17] VJ: They're both important.

[00:15:18] SY: They're both important. Ok. So my child has just passed the baton to its left child and now the left child will say, "ok now I have the baton. I'm gonna read myself. Gonna print that out." Now does it have a left child? No. Does it have a right child? No. So it is done. It hands the baton back up to its parent, which is my child. And now that whole left child situation is done for my child. So now my child has to go "ok cool. Now do I have a right child? Yes I do, patiently waiting." Hands off the baton to my right child. Now the right child is gonna read itself. We're gonna print that out. Then the right child is gonna say, "do I have a left child? No, I don't. Do I have a right child? No, I don't. Ok. I'm done." Hand the baton up to its parent. Now its parent is, is done. It's done its duties on its left. It's done its duties on its right. Now it's gonna hand the baton back all the way back up to me.

[00:16:17] VJ: And now you're done, too, because you've done your left...

[00:16:19] SY: Yeah.

[00:16:19] VJ: ...and your right.

[00:16:21] SY: Ok, so for my preorder strategy, I started with me. I started with the mom of the root. Then I ended up exploring and, and, and dealing with my whole left subtree, which is like the whole left half of my tree, my family. And then I moved over to the right subtree and then handled that and spit that out.

[00:16:43] VJ: And that kind of matches the DLR algorithm aspect, right? 'Cause...

[00:16:47] SY: Yeah, it does.

[00:16:48] VJ: ...data, left, right. That means...

[00:16:49] SY: Yeah. (Music)

[00:16:50] VJ: ...you're going to always have your root node come out first and then your whole left subtree and everything over there and then your whole right subtree.

[00:16:57] SY: And that wraps up our pre-order strategy. Next episode, we're gonna walk through an example of how the in order strategy works. That's LDR. Hopefully give you a clearer picture of what that actually looks like, but for now, that's the end of today's show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi's blog post. Link to that is in the 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:17:35] VJ: Bye, everyone.

[00:17:37] SY: Thanks for listening. See you next week.