Transcript from the "Pseudocoding the BST contains() Method" Lesson
>> Bianca Gandolfo: We're gonna pseudocode out contains, so I'm going to delete our pseudocode. I'll leave that down there so we know what our.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So here's our contains. So, what is the contain's interface look like? Like what is the input and what is the output?
>> Speaker 2: Input is a value.
>> Bianca Gandolfo: Hmm?
>> Speaker 2: Input is a value. And output is true or false.
>> Bianca Gandolfo: Yup. It takes a value, and we expect it to return true. Actually we just have to type true or false based on if we find that value in the tree that we're searching. Cool? That's contains.
[00:00:52] That's it. You can expect most contains methods to have this interface. Okay. So, who here has pseudo-coded out contains already, or coded it? Okay. Starting. What might be the first thing we want to check? Right, because for contains, we're going to be checking through the entire tree, well not the entire tree.
[00:01:22] We'll be checking through the tree as much as we need to.
>> Speaker 2: First I check this.value is equal to value?
>> Bianca Gandolfo: Yeah, so what if the root is what we need? And then we can just call it a day, right? So this again is going to be our tree and our tree.
[00:01:48] Instance is gonna be our root node, everything else points. Or everything else actually is inside of it, right? Because we have these nested objects. Okay, so is the current value = value?
>> Bianca Gandolfo: What about if it's yes?
>> Speaker 2: And it's true you can exit.
>> Bianca Gandolfo: [CROSSTALK] this is true, we over return, true.
[00:02:30] Sound good?
>> Speaker 2: Yes.
>> Bianca Gandolfo: What else do we have to check for?
>> Speaker 2: Well, you probably see if it's greater or less than the current values. So that you can know which direction to go.
>> Bianca Gandolfo: Yeah. Greater than or less than current value. Okay? Then what?
>> Speaker 2: So if it's greater go right.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: So if it is greater,
>> Bianca Gandolfo: Go right. I'm putting quotes around here cuz it's a little more complicated, but we've done this before.
>> Bianca Gandolfo: And then the other one is, check if it is. Less than right? And then we go left, we're gonna gor left, go left.
>> Bianca Gandolfo: What else?
>> Speaker 2: Nothing else.
>> Bianca Gandolfo: Nothing else? What if we don't find it?
>> Speaker 3: You go right, of course. Call contains again.
>> Bianca Gandolfo: Mm-hmm, yeah we can dig in to right means. So we're gonna call contains on the next node, right? How do we do that again?
[00:03:55] We just talked about-
>> Speaker 2: Whatever
>> Bianca Gandolfo: That right?
>> Speaker 2: That contains value.
>> Bianca Gandolfo: Yeah, call on the value.
>> Speaker 2: Did you say we have to go back right again or whatever?
>> Speaker 3: You're gonna have to return fall somewhere in there.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: If you don't find it.
>> Bianca Gandolfo: So if you just wanna just look at a picture really quick And what we're gonna be doing. So, if we're looking for, we're looking for let's say 19, right? 19 does not exist, if we're the computer we don't know that. So we start here at 11, we say, 11 are you 19?
[00:04:35] 11 says, no sorry I'm not 19. And then it says, okay are you less than? Is 19 less than you? And then it's like, no. Is 19 greater than you? Yes. And then we go right, right? We say this dot right contains, it starts all over again and it says, hey 15, are you 19?
[00:04:53] 15 says no and then says, but you know then are you less? Are you greater? If you're greater, go right and it says twenty are you nineteen? Twenty says no, then they check if it's less it is less. So we go a left and then say eighteen are you nineteen?
[00:05:14] Eighteen says no. Then you check to the right because its greater and there's nothing there.
>> Speaker 2: That means false.
>> Bianca Gandolfo: And then, that's when we know that we have not found it.
>> Speaker 2: But you would never have to backtrack, right? Because they're all ordered.
>> Bianca Gandolfo: Nope. Yeah, because its always ordered, so you always know that nineteen, if it's going to be anywhere.
[00:05:38] It's gonna be somewhere to the right of 18. And since there is there is nothing, there is no right sub tree of 18. There is no way that it exist in the tree and that's just the constraints of a BST. Cool. So that's how we do it.
>> Bianca Gandolfo: So we got the returning true part right.
>> Bianca Gandolfo: Should we do some stack tracing and kind of feel out what happens, and then see if we can find a place where it makes sense? Does that seem like a natural next step? Or does someone have a hunch?
>> Bianca Gandolfo: Okay, we'll feel it out. Let's open up our thing.
[00:06:24] Okay. Alright. So we're gonna look for we're gonna pass in 19. Okay? Here, I'll write it out
>> Bianca Gandolfo: So let's keep open our picture.
>> Bianca Gandolfo: Okay? So we can kind of look at the picture while we're doing the pseudocode. So we're gonna look for 19, what's the current value at the beginning?
>> Speaker 2: 11.
>> Bianca Gandolfo: 11, so they're not equal. So is it greater? Yes, right. So we go right, which means we recurse. We're gonna push another on to the stack,
>> Bianca Gandolfo: Right? And so current value.
>> Bianca Gandolfo: I'm gonna call current value CV, if that's okay with all of you.
[00:07:31] So current value for the right child is 15, right? CV here is 11.
>> Bianca Gandolfo: Are we following here, current value is 15. We've gone to the right.
>> Bianca Gandolfo: So, are they equal, false? Is it greater, true? And we're gonna go to the right again. So what's our current value the third time around?
>> Speaker 2: 20.
>> Bianca Gandolfo: Yup, 20. So we went, started here and we went right and we went right. We are at 20. Are they the same?
>> Bianca Gandolfo: Nope, is it greater? No. Nope, okay, so it is lesser. This is true. And then we're gonna go left.
>> Speaker 3: You would have to see if there's right and left.
[00:08:33] Yeah, so we wanna make sure there is a right or left because if we- Before you called it.
>> Bianca Gandolfo: Yeah, if we.
>> Speaker 3: That's the way you would know if it isn't there.
>> Bianca Gandolfo: Mm-hm, but let's just finish it and then we'll put in our checks.
>> Bianca Gandolfo: So 18, no.
[00:08:55] Is it greater? No.
>> Bianca Gandolfo: And then we have.
>> Speaker 2: The value, it doesn't change, right? It's 19. CV is 18.
>> Bianca Gandolfo: Yeah, well, we say this.left and there isn't even a left.
>> Speaker 2: I see. Right, so we might have an upset browser saying, you can't call contains of undefined or something some Something like that, which isn't saying no.
>> Bianca Gandolfo: So we're gonna have to check.
>> Bianca Gandolfo: Right? Where's our main.
>> Bianca Gandolfo: So like if there is a right, then you go right. If there is a left, then you go left.
>> Bianca Gandolfo: Then, what? We still haven't returned false somewhere.
>> Speaker 2: If there's not a right or there's not a left.
[00:09:56] To short or return false.
>> Bianca Gandolfo: Cool, but where should we put that in? At what point do we know there is no left or right.
>> Speaker 2: At the very end.
>> Bianca Gandolfo: Mm-hmm, yeah. So the easiest way to do this is just to return false at the very end.
[00:10:20] Something like that. Does that make sense? Because if it returns true, it's going to return true. Otherwise it's going to return false. There may be a bug here. That I want you to debug, when you implement. But this is on the right track. Are you guys ready to implement this?
[00:10:45] Yep. Okay. I'm going to say, is 20 minutes reasonable? Do you think? Or do you want 30 minutes?
>> Speaker 3: 20 and you'll check in.
>> Bianca Gandolfo: 20. Okay, I'll check in at 20.
>> Bianca Gandolfo: So, just to let you know what we're doing, we're going to our binary search tree, and we are going to finish implementing contains.