Tree and Graph Data Structures Count Recommendations
Transcript from the "Count Recommendations" Lesson
>> Bianca Gandolfo: Okay, so we're gonna revisit our original task, which is to count all the recommendations that our chat bot can make for us. So we discussed earlier that recommendations were the same as leaves on a tree, and we define a leaf as a node that has no children, yeah.
[00:00:24] So let's check that out. I have here our contains that we were working on earlier, to kind of have a reference of how maybe we can work with this and also to compare, right? So the difference here, this is a class method, so we're using this. CountReccos is a function that we pass a tree, okay?
[00:00:48] So again, we're not gonna be using this is in all of that. All right, so the first thing we wanna do is see if,
>> Bianca Gandolfo: If a tree or a node, we can just call this a node. If a node is a leaf, how do we check that again?
>> Bianca Gandolfo: Node.left?
>> Speaker 2: And node.right.
>> Bianca Gandolfo: Sorry, and,
>> Bianca Gandolfo: So this is if they have it, this says if they don't.
>> Speaker 2: No dot, no.
>> Speaker 3: That's right or yes, no.
>> Bianca Gandolfo: Just testing you. Are you really paying attention? Okay, so if we don't have children, then it's a leaf and we want to return something,
>> Bianca Gandolfo: Okay? I don't know yet, I'm just gonna return. Otherwise, we need to keep traversing, right? So,
>> Bianca Gandolfo: We can kind of copy this here, let's just start with one. We'll copy this, so this is gonna be traversing through the left, but we don't want to do contains, right?
[00:02:32] So we're gonna change this to node, if node.yes and
>> Bianca Gandolfo: We want to do something. What do we want to do with this? We wanna keep counting, right, where this is gonna be a recursive solution.
>> Bianca Gandolfo: So we'll call that, and we're gonna need to do something really similar for the right side as well.
>> Bianca Gandolfo: Everyone following here?
>> Bianca Gandolfo: Okay,
>> Bianca Gandolfo: Let's just keep this or operator here. Let's check it out. Let's just try this and see what happens. Does anyone have a guess of what's going to happen, what this will return?
>> Bianca Gandolfo: Sorry.
>> Bianca Gandolfo: First of all, it's not gonna return anything.
[00:03:26] Yeah [INAUDIBLE] a Boolean.
>> Speaker 4: Will it always be false if we're returning an empty string?
>> Bianca Gandolfo: Yeah.
>> Speaker 4: It'll return an empty string eventually.
>> Bianca Gandolfo: Yeah, eventually, you will always return an empty string, and it will be false. Okay, so we don't need to walk through it cuz we know that, good.
[00:03:46] But what do we wanna return? We wanna return that we found a node. So I'm gonna recommend that we return 1.
>> Bianca Gandolfo: Okay, now we're out of the boolean, sort of. Now, how does this change? So once we get to the bottom, we return 1.
>> Speaker 2: We need to figure out a way to add up our 1s.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: That go through the recursion.
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Let's walk through it. And let's see if we can identify where that is. All right, we're gonna use our tree over here and we expect there to be two leaves, right? B is a leaf, D is a leaf.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Go away. All right, so the very first time we call it, node is A, right?
>> Bianca Gandolfo: Does it have a left and a right? Yeah, so we're gonna skip over. Does it have a left?
>> Bianca Gandolfo: Yes, so we're gonna call this again with the node in question, which is the B.
[00:05:13] So does it not have a yes and does it not have a no? True, we return 1.
>> Bianca Gandolfo: Okay, pop this off, and we called it here, remember?
>> Bianca Gandolfo: Okay, now we're gonna go here.
>> Speaker 6: It won't go there, right? Once the-
>> Bianca Gandolfo: That's true. We have our operator here, that's annoying.
[00:05:46] Well, let's just change it for now. So then we have to go to the next one. Good catch.
>> Bianca Gandolfo: We'll go to no.
>> Bianca Gandolfo: That's really interesting that it keeps doing that. Okay, we'll go to C. So what did we call?
>> Bianca Gandolfo: Okay, so this one is C.
[00:06:11] Is C a leaf? No, so it's going to do this thing.
>> Bianca Gandolfo: Okay, so it's going to then traverse to the left. Doesn't have a left, right? So this is gonna be false,
>> Bianca Gandolfo: Or flash. False, okay?
>> Bianca Gandolfo: Uh-oh, now we have that problem again. Now it's false.
[00:06:56] So this is wrong, right? That needs to change for sure. Because we do want to go to the right, correct?
>> Bianca Gandolfo: Right, right, uh-huh.
>> Bianca Gandolfo: Okay, so this is wrong. So we need to change that.
>> Bianca Gandolfo: And let's just move on and just note that that's not correct.
[00:07:20] We'll go to node.no, which is D. We're gonna call this again.
>> Bianca Gandolfo: And this is a leaf node, so we don't have to worry about all of that. And this will return one. Okay,
>> Bianca Gandolfo: Right, returns one, everyone following? Cool.
>> Speaker 7: We still haven't counted, right?
>> Bianca Gandolfo: Hm?
>> Speaker 7: We still haven't counted it?
>> Bianca Gandolfo: No, we have not. What you see is what you get, this is where we're at. So we popped it off and we return 1 here. So now we have some interesting things happening, right? We have false, this is true,
>> Bianca Gandolfo: Right, some weird things.
[00:08:22] But we're getting somewhere, we're returning numbers. At least in two parts of this, we have 1 and 1 somewhere, right?
>> Bianca Gandolfo: So we're gonna need to add these, and the question is how? And we also have the issue of this true and false. It seems like it's adding some logic that is gonna take away from the solution.
[00:08:45] Thumbs on that read? Okay,
>> Bianca Gandolfo: Cool, so what if we changed this to plus.
>> Bianca Gandolfo: Actually, this returned undefined, right? What did this return? This just returned false because of our boolean. So what if we,
>> Bianca Gandolfo: Did something like this, I keep deleting the things that I need.
[00:09:22] Let me put it back.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So let's maybe skip this check, skip this check. So we're taking some risks here. We might be passing undefined, right, or null.
>> Bianca Gandolfo: But at least we don't have to worry about this kind of stuff is getting in the way.
[00:09:53] It's not helping us.
>> Bianca Gandolfo: Okay, so now we have the issue that we are gonna be adding booleans and stuff. Well, we don't have this one. But this one is now, it's not gonna be false anymore. This is now gonna be returned undefined, right? Do you guys understand why that is?
[00:10:22] So once we go to C,
>> Bianca Gandolfo: Right, we're gonna call this. Let's just go through one with our new,
>> Bianca Gandolfo: Our new strategy here. So now, we call this one with null, right? You see that because here's undefined because we pass null and we're not handling the case for where there's nothing there.
[00:10:54] So we pass null. This is not gonna work out for us, there's nothing there and then we're gonna return, all this is not gonna help. So I'm just gonna do another check up here, If (node === null), right? This is like what we were checking before, we were safeguarding.
[00:11:23] Return 0, right? We need a number, we're adding. So now, when we pass in this nothing here, which is c.yes, it's gonna be null, we return 0. So now we have 0 here.
>> Bianca Gandolfo: How do we feel about that?
>> Bianca Gandolfo: All right, we'll pop this off. Let's move this to our final solution.
[00:11:56] So we're popping this off. Now, we're returning 1 + 0, okay, from here. So right, 1, so this is now 1,
>> Bianca Gandolfo: 2.
>> Bianca Gandolfo: Easy, right? [LAUGH]
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: Just kidding, but do you see how I reason through that? We're like, okay, this boolean thing is not what we want.
[00:12:37] We want a number, let's get rid of it. But we still need to make sure that we're dealing with null, how do we do that with a number? Okay, 0, like,
>> Bianca Gandolfo: That's the strategy.
>> Bianca Gandolfo: I need one question from the audience.
>> Bianca Gandolfo: Can you gift it to me?
>> Speaker 8: Is there another way to do this?
>> Bianca Gandolfo: You can do it iterably and you can keep a variable.
>> Speaker 8: That's the way I would have done it [LAUGH].
>> Bianca Gandolfo: Yeah.
>> Speaker 2: So you don't need an accumulative value to catch the one coming from two different spokes even if they are nested?
>> Bianca Gandolfo: If you're finding that you're losing your value, it's cuz you didn't stand up for yourself, no. It's because you didn't return somewhere properly.