Description

Let's dig into another depth-first search strategy: in-order! This time, we walk through a numerical example, traversing the tree with fresh, animated voices and a broken washing machine. And when you're done learning all about inorder, take our postorder challenge! Tweet us the output of a postorder strategy applied to this binary search tree. Make sure to use the #basecs hashtag, and no cheating! :D

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:12] SY: And she is the brilliant mind behind the basecs blog series. Today we're continuing our conversation about...

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

[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:11] SY: We are continuing our conversation on depth-first search and the different strategies we can use to implement it. Am I saying that correctly?

[00:01:21] VJ: Yeah

[00:01:22] SY: Is that right? Ok.

[00:01:22] VJ: Well those were all words. (Laughing) Those were all English words.

[00:01:27] SY: Yes. Nailed it.

[00:01:29] VJ: It made sense to me.

[00:01:30] SY: Just killed it. Ok, before we talk about strategies, let's do a quick recap of depth-first search. What is that?

[00:01:37] VJ: Depth-first search as we have been, you know, kind of revisiting (Laughing) in each episode...

[00:01:43] SY: Diving deeper and deeper.

[00:01:44] VJ: Yeah. At this point we're real deep. Deep into DFS. Depth-first search is one of the ways that you can traverse through a tree data structure and also graph data structures. And the main idea behind it is that it's an algorism where you traverse down the branch of a tree down a long path and then work your way back up, which is different from breadth-first search where you go level by level as you traverse through the tree.

[00:02:13] SY: Yes, and what I found so fascinating about this is this is all in the context of what you can do with a node, like how you interact with a node, especially when we talk about the strategies because there's really only three things that we can do with a node. We can ask it for its data. We can see if it has a left subtree, and then we can see if it has a right subtree. And the three strategies are just the different orders in which we can do those three things.

[00:02:41] VJ: Exactly. Yes. And that's actually a great way to kind of segway into a quick recap of last week's episode where we talked about one of the strategies, a type of depth-first search, which is pre-order where you basically follow the DLR rule. DLR, as a reminder, stands for those three things you just described. Reading the root node's data first, and then looking at the left child and then the right child and recursively implementing DFS as you go along. But today, we're gonna talk about a different strategy that is not DLR. We're going to kind of switch around the DLR into LDR, which is what we call in order—in order depth-first search traversal, which means that you're going to look at the left node first, read through its subtree and then you're gonna read the data of the node that you're on—the root node. And then you're gonna look at the right node and its subtree and recursively go through that.

[00:03:39] SY: Well let's do it. So let's try this one with a numerical example. Ok, we're gonna see if we can do this. Ok, you ready? Ready?

[00:03:46] VJ: Yes. I'm ready.

[00:03:48] SY: Ok. So we start with six—should we start at the top or at the bottom?

[00:03:55] VJ: Yeah, let's—I mean let's maybe describe the tree because this will be a good recap of binary trees. So binary trees—I'm just gonna describe it. Ok. (Laughing)

[00:04:03] SY: Just do it.

[00:04:04] VJ: Here we go. So since we're doing numbers and since we're dealing with binary trees, we can pick like a nice—a smallish one, nice small little binary search tree family. And so there is one root node. The root node is six. And six has a left child and a right child as you do when you're a binary tree. The left child is four, and the right child is eight. So let's look at the left subtree of six's family. So six has a left child of four, and four has two children. And if you'll remember with binary trees, anything to the left has to smaller than the root. And anything to the right has to be bigger, which means the left has to be smaller than four, and the right has to be bigger than four. So in this situation, four has two children. Its left is two and its right is five. And then five doesn't have any children. That lineage stops there. But two has two children: one and three. So one is going to be on the left of two because one is smaller than two, and three is going to be on the right of two because three is bigger. So we have six and then to its left four. Four has two five and two has one and three as its children.

[00:05:20] SY: Nice.

[00:05:21] VJ: Now let's go back up to six for a second. That's still our root. On the right subtree of this family, six has a right child of eight, and eight has two children. Its left is seven, and its right is nine. So we have the numbers one through nine represented in this binary search tree. Everything smaller than six lives on the left subtree, and all of the children that are bigger than six are in the right subtree.

[00:05:48] SY: Ok. That's pretty good.

[00:05:49] VJ: Yeah. So let's, let's see if we can get through this example with in order 'cause pretty...

[00:05:55] SY: Ok.

[00:05:55] VJ: ...pretty interesting when you start, you know, looking at numbers with it.

[00:05:58] SY: Yeah. Ok. So with in order, the first thing is looking to my left. It's the "L." So we always start at the top. We always start at the root, which is my six. But the first step is not actually doing anything with the value of six, it's just saying look to the left of six. So I go to the left of six, and as you mentioned, my six has two children: four and eight. Four is smaller so it's on the left side. It's the left child. So now I go down to four. So now that I'm at four, I restart my in order algorithm again 'cause now I have like a, like a new, a new parent node thingy. So at four, I say ok now I need to start over, which means starting back at "L." So I say, "ok four, do you have a left child?" "Why yes, I do." (Laughing) Because four has...

[00:06:53] VJ: Oh this is good. We should definitely do voices.

[00:06:55] SY: Right? Should do more voices always. So four has two children: two and five. Two is the left child because it is smaller than five. So when I look to the left, I'm looking at two. So now I'm at two. And now I have to restart my algorithm all over again. We're back at the "L." So now, I'm gonna say to two, "do you have a left child?" And two is gonna say, "in fact I do. I have two children: one and three." One is the left child because it is smaller than three. So now we're gonna go all the way down to one. So let's just take a moment to appreciate the fact that we've really done nothing. (Laughing) We just came... we...

[00:07:38] VJ: We just met like the baby, baby of the family. That's all we've done. We're like, "oh, hello."

[00:07:43] SY: I'm imagining, I'm imagining someone like trying to have a conversation with the parent, and the parent's like, "I don't have time to talk to you, but here's my child.” And then child is like, "I also don't have time to talk to you. Here's my other child." And that child's like, "I also don't have time to talk to you. Here's my..." And then the final child is like, "dammit, I don't have any children."

[00:07:58] VJ: You're just holding an infant by the end, and you're...

[00:08:00] SY: Yeah.

[00:08:00] VJ: ...like, “what did I do?" (Laughing)

[00:08:02] SY: Like what do I—I have to, I have to engage.

[00:08:04] VJ: This is not what I was here for.

[00:08:06] SY: Ok. So we've done nothing. All we've done is just looked. We've looked to our left. We keep finding a left child. So then we keep saying, "ok, well now we have to start over." Then we find another left child, and we've just gone all the way down. So we started up at the root, and now we're all the way down at one, which is one of our leaves. So now that we are at one, we're gonna say, "ok, do I have a left? No I don't." Oh. Something different has happened. And now, because the operations are LDR, I just looked at my left, got nothing. But now, I have to do the "D," which is looking at myself and saying, "Oh, I'm here. I'm gonna, I'm gonna talk to you now. Hello, my name is one." And now we would print out that one. And we just finished the "D." And now the last step is the "R," which is finally—we haven't looked at any right children so far—looking at the right and saying, "do I have a right child here? No I don't." And now I have completed all of my, my little, my little operations. I've, I've finished my, my algorithm for that one. That one section resolves itself.

[00:09:17] VJ: And all you've printed out...

[00:09:18] SY: All I've printed out... (Laughing)

[00:09:19] VJ: All you've printed out is one. I just wanna mention that's it.

[00:09:22] SY: All I've printed out is just one. And now I resolved all that. Now I can kick it back up to two. So now that I'm back at two, finally we've resolved the left child situation of two. So now we're gonna continue—and this is like the interesting part that I think is really fascinating is it's not that we're restarting our algorithm the way that we were thus far, it's that we're finishing the algorithm that never finished before.

[00:09:51] VJ: Yeah. You're resolving the unresolved part. You basically...

[00:09:55] SY: Yeah.

[00:09:55] VJ: ...were like, "I'm gonna go do 'L.'" And then you were like, "alright. Go off and do 'L.'" And now you've come back and you're like, "I finished 'L.'" And it's like "great. Well let's pick up where we left off."

[00:10:04] SY: Yeah, it's like when you start a chore and then you realize that chore involves like six other chores. And then you do one and then it involves like—it's all of these like hidden chores. And then you, you, you realize like, "oh my God. I finally am able to fold my laundry." (Laughing) You know? Like that's not even...

[00:10:17] VJ: You had to go buy detergent.

[00:10:19] SY: You had to go—yes. You had to go buy detergent.

[00:10:20] VJ: The washing machine was broken.

[00:10:21] SY: The washing machine's broken. (Laughing)

[00:10:22] VJ: Ordered a part. Suddenly it's two weeks later, and you're like "what was I gonna do again?" Now you're back there.

[00:10:29] SY: Yeah, so when we are back at two, we are continuing our original LDR function call. And we just finished, we just resolved the "L" part, which means now we have to go to "D," which is two saying, "hey, I am here. I am two." And then we can print the number two. And then after we do that, we can finish, continue with the algorithm and finish by looking at the right child. So before we continue, let's just do a recap of what we have so far. We've printed the number one. We've printed the number two. And that's it. That's all we've done so far.

[00:11:06] VJ: Yep. And all we've really done is we've looked at—we've resolved the left part of the algorithm for two, and we've resolved the data part of the algorithm for two. (Laughing) So we've only done "L" and "D" for one node...

[00:11:20] SY: Yeah

[00:11:20] VJ: ...so far. Well, I guess technically that's wrong. We've done LDR for one.

[00:11:25] SY: Yeah. That, that's true.

[00:11:26] VJ: And then we went up.

[00:11:27] SY: That's true.

[00:11:27] VJ: And then we did "L" and "D" for two. And now we're about to do "R" for two.

[00:11:31] SY: So basically we have bought the spare part that we need for our dishwasher, and we have someone coming over to fix it.

[00:11:41] VJ: Sure.

[00:11:42] SY: But we're still a couple steps away from having filtered laundry.

[00:11:44] VJ: We, we got a lot to do.

[00:11:46] SY: Ok, so now that we've done like you said the "L" and the "D" for two, now we're gonna do the "R," looking to our right. And our right child is the number three, which means that now we're gonna go to three and we're gonna say, "ok, three, do you have a left child?" Again we'll be starting our algorithm. Three does not have a left child 'cause it is a leaf. We're at the very end there. So there's nothing, nothing to do there. So now we move on to "D," which is saying, "three, what are you?" Three says, "hello, I am three." We (Laughing) print out, we print out three. These numbers don't really have that much to say. (Laughing) And then...

[00:12:30] VJ: They're simpletons, you know? They like the simple life.

[00:12:32] SY: They're simple people, simple people. And three, we, we say to three, "ok, do you have a right child?" Three says no. And we say, "ok, cool." We have finally resolved the three situations. We can kick it back up to two, and holy smokes, I think we are, I think we're done with the, the two subtree.

[00:12:53] VJ: We finished two. We finished...

[00:12:55] SY: We finished...

[00:12:55] VJ: ...its children, one and three. And we've...

[00:12:57] SY: Yes.

[00:12:58] VJ: ...printed out one, two, three.

[00:12:59] SY: Oh.

[00:13:00] VJ: We printed out the left, the data and the right. The data is also the root of that little mini subtree.

[00:13:06] SY: Little mini subtree.

[00:13:06] VJ: So like one, two and three.

[00:13:07] SY: Yeah. Ok, but two is actually the left child of four. So by resolving that two, one, three little subtree situation, we've also resolved the left part of the four, of its parent.

[00:13:24] VJ: Yep.

[00:13:25] SY: So now we can go up to four. And now that we've finished its left child situation, we get to move on to "D" in the algorithm and say, "four, what are you?" Four says, "hello, my name is four." Did you notice that four is a little more friendly? It said hello first before it told you what it was.

[00:13:41] VJ: Its manners did not pass down to its grandchild.

[00:13:43] SY: It did not. It did not do a good job. (Laughing) And so, and so four says, "hello, my name is four." So we print out four. And then we continue with the algorithm, which is looking to see if it has a right child. We look to its right, and we say, "oh, look. There is a child there." Now we will go to its child, which is five.

[00:14:06] VJ: Yep.

[00:14:07] SY: So so far we've printed out one, two, three and we just printed out four. So now that we are on five, now we have to start our algorithm all over again and say, "ok, five, do you have a left child?" "No I do not." "That's fine. Five, do you have yourself?" "Yes, I do."

[00:14:27] VJ: I'd hope so.

[00:14:28] SY: I'm... (Laughing)

[00:14:29] VJ: I don't know what you'd do if you misplaced that.

[00:14:33] SY: "Here is who I am. I am five." Great. We're gonna print it out, print itself out.

[00:14:36] VJ: Very existential.

[00:14:37] SY: Very existential, and there's a lot of self-reflection in, in, in these (Laughing) depth-first searches. And then we're gonna say, "ok, five, we're gonna continue with the algorithm," which is going to its right child. We're gonna say, "five, do you have a right child?" Five is gonna say, "no, I do not." We're gonna say, "ok, we are done with you. You're dismissed." It is resolved. We go back up to its parent, which is four. And at this point, we just finished the right child. We already did the "D" part, and we already did the left child part, which means our four subtree is now completely resolved.

[00:15:15] VJ: Yep. Four's, four's left subtree was done. We finished four. And when you finished four's right subtree, which was actually one little node so it's fine—the existential one with no children. That's five for ya. Typical five. (Laughing) Questioning everything.

[00:15:31] SY: These fives.

[00:15:34] VJ: So we have printed out one, two, three, four and now five.

[00:15:39] SY: So now that we've resolved that four subtree, we can go to the parent of four, which is six. And now, you might notice, that we are back at the very, very, very top of our tree. We're back at our, at our root of the main part of our tree, which is six. And...

[00:15:55] VJ: Finally the parent gets some, some, you know, attention.

[00:15:58] SY: Some love. Some attention, some attention. It's like I've been waiting this whole time. (Laughing) That's my parent voice.

[00:16:05] VJ: It's very accurate. I like it.

[00:16:08] SY: Right? Get out of the forest. Yeah, yeah, yeah. There's too many leaves down there.

[00:16:20] VJ: That's my favorite one. I like it.

[00:16:24] SY: Oh my God. I'm gonna make myself cry. Ok, so what is again interesting about this is that we never left our—I think it's like our original function, right? Like our very, very, very, very first function when we first started with six and said, "do you have a left child?"

[00:16:43] VJ: Yeah. We're still in the process of the...

[00:16:46] SY: Of answering that question.

[00:16:47] VJ: ...of the LDR, the original LDR, which means we haven't finished.

[00:16:50] SY: The original LDR.

[00:16:51] VJ: Yeah.

[00:16:52] SY: We have not finished. Right.

[00:16:53] VJ: We finished one part.

[00:16:54] SY: We just got an answer. It's, it's so fascinating. So now we are done with the left part of LDR for our very, very first function, for that six, which means that we can now ask the parent, "hey, parent, who are you?" And the parent will say, "I am six." And we can print out six. Now we have one, two, three, four, five and we just printed out six.

[00:17:21] VJ: And we have one last step left in the LDR process. Finally. We've gotten through "L" and "D."

[00:17:27] SY: In the original...

[00:17:29] VJ: Now we just have to get...

[00:17:29] SY: ...LDR

[00:17:30] VJ: ...through "R."

[00:17:30] SY: The "OG" (Laughing) LDR. Yeah. Ok, so let's do this. Now we're gonna say, ok we have, we did the left, we did the "D." Now we're gonna do the right. So now we're gonna say to the root, say to six, we're gonna say, "hey, do you have a right child?" And it's gonna say, "yes, I do." (Laughing) And then we're gonna...

[00:17:50] VJ: These voices get better and better as we get further and...

[00:17:53] SY: Right?

[00:17:53] VJ: ...further into this traversal. It's the best.

[00:17:56] SY: Like a fine wine. And so now six goes to—we go to the child of, of six, the right child of six, which is eight. And we say to eight, "hello, eight. Do you have a left child?" Because again, we're starting all over again with our, our algorithm because we have a new, a new node. And we say, "eight, do you have a left child?" And eight says, "yes." And the left child for eight is seven.

[00:18:25] VJ: Yep.

[00:18:26] SY: So now we're at seven and we say, "ok, we have to start our algorithm all over again." So now, we're gonna say "ok, do you have a left child?" And seven is gonna say, "no, I do not." Ok. That's fine. So now we're gonna say, "seven, who are you?" And seven will say, "seven." Very abrupt.

[00:18:40] VJ: Yeah.

[00:18:41] SY: Very, very short. Just doesn't have time.

[00:18:43] VJ: Snappy. It's got places to be and things to do.

[00:18:46] SY: It's a New Yorker. Ok, that's what it is.

[00:18:47] VJ: It's, it's a prime number.

[00:18:49] SY: There you go.

[00:18:50] VJ: You know what that means

[00:18:51] SY: A little diva-ish. A little diva. (Laughing) And then we're gonna say, "do you have a right child?" And it's gonna say, "no, I don't." And we're gonna say, "ok, we are done with you. You are resolved." So now we've printed out our one, two, three, four, five, six. And we just printed out our seven. Now that that's resolved, we're gonna go back up, kick it up to the parent, which is eight. And from that parent's perspective, we just finished the left child part of that algorithm. So now we have to go to "D" and say, "who are you?" And it's gonna say, "I am eight. I like to eat. I just ate." Eh, eh? (Laughing) You get it? You get it? No? All right. That's fine. (Laughing) And then we're going to, to ask it, "ok, now that we've, we know who you are, we've printed you out," now we're gonna say, "do you have a right child?" And it does. It has a right child. And its right child is nine. So now that it has a right child, we have to start our algorithm all over again. Hopefully this is the last time. I think this is the last time. And we're gonna say, "ok, right child, do you have a left child?" And it's gonna say, "no, I do not." And we're gonna say, "ok, great." 'Cause we're kind of tired of doing this, this...

[00:20:06] VJ: Yeah.

[00:20:07] SY: ...this algorithm. And we're gonna...

[00:20:08] VJ: It's taken a long time. (Laughing)

[00:20:10] SY: It's been a while. It's been a while. A lot of work going on. And we're gonna say, "ok, who are you?" It's gonna say, "I am nine." And we're gonna say, "ok, do you have a right child?" "No, I do not." Done. Resolved, which means we get to kick that back up to eight.

[00:20:23] VJ: Passes the baton back.

[00:20:24] SY: Kicks its baton—not necessarily. You don't kick a baton. Passes the baton (Laughing) back up. And now it's like—how does batons work? Twirls, twirls it's baton back up.

[00:20:33] VJ: Oh, fancy. Nine is the show off.

[00:20:35] SY: Fancy. This is the fancy side of the family.

[00:20:39] VJ: Of course.

[00:20:39] SY: And so now that we've done that from the eight's perspective, we resolved its left child situation. We already read who it is. We know it's an eight. And we just resolved its right child situation. So eight is also done, which means we've resolved that little subtree, which is also the, the right, the right subtree. And now we get to pass the baton one last time all the way up to six.

[00:21:06] VJ: Who at this point is probably like God knows how old waiting for this... (Laughing)

[00:21:10] SY: Yeah.

[00:21:11] VJ: ...algorithm to finish. It's like six is like come on. Come on, kids.

[00:21:14] SY: Fall asleep, taking a nap. And so when we resolve it and we're back up to six. That means that we've finally resolved the right child situation of our very, very, very first function call. The very, very first one when we started the root and we said, "do we go left? Do we go right?" Like we finally resolved the right side of that.

[00:21:34] VJ: Yep.

[00:21:34] SY: And as a prize for doing such a great job, we get this amazing list. And it reads: one, two, three, four, five, six, seven, eight, nine. (Laughing) Which is...

[00:21:48] VJ: So much work for that.

[00:21:51] SY: It's a lot of work for, for what that was. But we get an ordered list.

[00:21:56] VJ: Yeah, we get an ordered list in which the root node is smack dab in the center. We have the left subtree—everything smaller than six, all the numbers smaller than six in a binary tree are before it. And then you have the root node printed out right in the center: six. And then you have the right subtree: seven, eight, nine. That little, you know, mini family is all to the right. So now you have "L," "D," and "R": left, data, right. All in printed out in order.

[00:22:23] SY: Yeah.

[00:22:23] VJ: Which is great in binary trees because the in order traversal, the in order strategy for depth-first search will give you an ordered list, which can be really handy if you have a massive tree. You can be like, "well, I wanna get these in order. I wanna sort these."

[00:22:38] SY: Yeah.

[00:22:39] VJ: Well I know which algorithm I wanna use.

[00:22:41] SY: Yeah. Absolutely. Ok so we are not gonna do post-order, 'cause as you saw, this took a really long time. Instead, we're gonna have you do the post-order. So post-order is LRD. So you are going to take our binary tree example—and we'll put it in the show notes just so you have that, a nice visual. And your job is going to give us the LRD printout. What is our list of numbers gonna look like when we're done with our depth-first search using the post-order strategy?

[00:23:13] VJ: How are they gonna give it to us?

[00:23:14] SY: They can tweet us. They can tweet us using the basecs hashtag.

[00:23:20] VJ: Perfect.

[00:23:20] SY: I think that'll work.

[00:23:21] VJ: Yeah.

[00:23:21] SY: Right? That's a good one.

[00:23:22] VJ: That's awesome.

[00:23:22] SY: A good way to do it.

[00:23:23] VJ: (Music) All right I can't wait to see all your numbers in some order.

[00:23:27] SY: And no cheating, ok? No cheating. No looking at other tweets (Laughing) before you... And retweets don't count. Ok? Retweets don't count. You gotta do your own. You gotta do your own. Awesome. And 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 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:24:05] VJ: Bye, everyone.

[00:24:06] SY: Thanks for listening. See you next week.

[00:24:10] VJ: We should've just kept going and then I doubted myself. Story of my life. Ok. (Laughing)