Binary Tree contains Solution

[00:00:00]
>> Bianca Gandolfo: Let's adapt this, to contain. So what contains does is it takes a value and it looks at every node in our tree and returns true or false if we have that value in our tree. Cool, so, maybe we want to check if we have a particular question or a particular recommendation.

[00:00:25]
Right, again, just to note, if we have a recommendation, we can just add another field called recommendation. But it would be the same, the logic would be the same.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So what do we do first?
>> Student: Take the value.
>> Bianca Gandolfo: Yeah, if the first, so if this.question,

[00:00:59]
>> Bianca Gandolfo: Let's keep it so if this.question === question, we return true.
>> Bianca Gandolfo: Yeah? All right, that's the first one. Now we need to deal with the nested. What if, so we know that this is gonna be recursive, right. Why do we know that?
>> Student: iii
>> Bianca Gandolfo: Yeah, because we need to traverse it.

[00:01:33]
So it's gonna be really similar as our traverse.
>> Bianca Gandolfo: But also a little bit different, right? Because we're returning a value here. With recursion we need to preserve that value that we're returning. So there's some considerations. But let's take it from step one. Let's imagine that we only need to check the next children.

[00:01:57]
So we can then say contains.
>> Bianca Gandolfo: This will check all the left, sorry, also this needs to say this.
>> Bianca Gandolfo: Okay? So what happens here. Let's break it down. So let's look at, where is our data structure? Let me grab one from a slide. Here we go, okay.

[00:03:03]
>> Bianca Gandolfo: Okay, so we have our question, we have yes and we have no, right?
>> Bianca Gandolfo: And we want to see if, let's look for,
>> Bianca Gandolfo: Something that exists here.
>> Bianca Gandolfo: Okay, let's see. Do you like butter? I don't know. Something like that. So that's just another node with a question.

[00:03:39]
So we're gonna check the first one if it contains yes. So how does that work? So we start with the first question, we're looking for, do you like butter?
>> Bianca Gandolfo: First question is, do you feel like cooking? Is that equal to question? No, so it's not gonna return true.

[00:04:01]
We call contains with this.yes of that, so the yes is do you have milk? If we go in here, do you have milk does not equal,
>> Bianca Gandolfo: Do you have butter? Do you guys see the bug? What does this say?
>> Student: You're not going one level more?
>> Bianca Gandolfo: So this says, do you like cooking?

[00:04:32]
>> Student2: Well, it's taking [CROSSTALK]
>> Bianca Gandolfo: This is gonna say, do you like cooking?
>> Student2: Yes, so it's gonna be an object and it's gonna be a tree.
>> Student: It should be this
>> Bianca Gandolfo: You guys see that? So this.contains, if we pass this .yes, the problem is that we are overwriting, first of all, we're overwriting this.

[00:05:09]
So let's look at it with the value. So this question is, do you have milk. So then we're changing the question here. See the problem there?
>> Student2: I don't think that we should be calling this.contains. I think we should be calling this.yes.contains.
>> Bianca Gandolfo: Mm-hm. How is that different, this.yes.contains and then we pass the question in there.

[00:05:43]
>> Bianca Gandolfo: Now, we pass question,
>> Bianca Gandolfo: To that,
>> Bianca Gandolfo: And we preserve the value of question. See the difference there?
>> [INAUDIBLE]
>> Bianca Gandolfo: Cool, all right. So let's take it from here. So this.yes.contains question. We pass it in. We have the whole node, right, not just the string, this.question = question.

[00:06:21]
So it's does do you have milk equal do you like butter? No. This.yes.question, [SOUND]. So we keep going, right? It's gonna keep going. Eventually this is gonna air out, right? So we have to say if this.yes. See the similarity here?
>> Bianca Gandolfo: And what else do we need to do here?

[00:07:00]
>> Bianca Gandolfo: We wanna traverse the right.
>> Bianca Gandolfo: And then, what about that return value? If this returns false this will, might short circuit our recursion prematurely, or it might not. Or maybe we need to store it. Let's investigate. All right, so the question here is do you like butter?

[00:07:39]
>> Bianca Gandolfo: And let's start. Okay, so question, do you feel like cooking? This is not,
>> Bianca Gandolfo: Not gonna enter this.yes. Do we have a yes, true. So then we're gonna go into that, which is do you have milk? It's gonna come in here. This.question is gonna be do you like milk?

[00:08:07]
This is gonna be fo you like butter? Nope. It's gonna go in here again. And whatever that is there is also not gonna return true, and so, it's going to then skip to the no. See that? The no of this one.
>> Bianca Gandolfo: And then it's gonna go through all of the no's, or it's gonna go through the no, and then the yes of that no.

[00:08:47]
>> Bianca Gandolfo: Because we're gonna call, so if you say this.contains with a no, it still is gonna call this one first. So what this is doing is it's checking itself. It's checking all the left. Then it's checking the right one and all the left ones. The right one or the left ones like that.

[00:09:08]
But we're still not really returning anything. Let's imagine that we get to the bottom of this. The bottom of this, so we haven't found this yet. How do we return this value? How do we get this out, right? So we could return return, right?
>> Student: We can't have two return statements.

[00:09:41]
We can actually, I think we should put a variable up there, like contains and put another why logic until that is true. Until that as far as we keep doing this once that is true we stop doing.
>> Bianca Gandolfo: Yeah. So using a while loop with our recursion and then kind of holding a value, what if we just did something like this?

[00:10:20]
>> Bianca Gandolfo: And that works.
>> Bianca Gandolfo: So, if one of the yesses has a question, or this one has a question.
>> Student: What about that break when you get to the end?
>> Bianca Gandolfo: Would it?
>> Student: It'd return to false if nothing has it.
>> Student3: But what happens when this.yes is null?

[00:10:54]
>> Bianca Gandolfo: What happens if yes is null? You can have a check in there. So it's,
>> Bianca Gandolfo: You can check, can guard.
>> Bianca Gandolfo: Okay, so this will check if this is true, what does that do?
>> Student3: If we get to the case where there's no yes and there's no no property, this will return false.

[00:11:29]
So that'll be our bottom of the pyramid.
>> Bianca Gandolfo: So, you're saying that, if this is, we get to the bottom, and this is nul, right?
>> Student3: Yeah, if that's null, this .yes will be evaluated as false. Then this.yes.contains question will run and it will look at the or.

[00:12:02]
And if this.no evaluates to false, it won't run this .no.contains question.
>> Bianca Gandolfo: Yeah.
>> Student3: Does that return false? Will that return false then?
>> Bianca Gandolfo: Yeah, so if we get to the bottom, this will return false. But what if we went in here first? Are we able to preserve this value?

[00:12:27]
That's the real question, right? So, is this carrying over?