Binary Search Solution

[00:00:00]
>> Bianca Gandolfo: We're gonna go over the binary search exercise. So just a reminder, we both implemented the constructor portion, the insert method, as well as the contains or search method, cool?
>> Bianca Gandolfo: Let's take a look. So the constructor of the binary search tree is pretty simple, actually. It just has a pointer to the root node.

[00:00:28]
But with that said, we do need another constructor that constructs the actual nodes. This is pretty common when you're creating a tree, to have a separate constructor for the node. And then, you insert that node into your tree, okay?
>> Bianca Gandolfo: All right, so let's take a look first at the insert.

[00:00:51]
Just a reminder, when we are inserting a value into a binary search tree, it has to traverse through and find an empty space where it follows the rules where a left child has to be less than the parent node, and the right child has to be greater. So as we're traversing, there are certain rules that we have to follow to insert.

[00:01:18]
We can't just insert it anywhere we want like with our binary tree or our tree. All right, so let's check this out. So we have an insert helper here.
>> Bianca Gandolfo: And we basically just initialize it. And you'll see why we have the helper in a second recursion. We have a insertHelper here.

[00:01:43]
It's just going to call itself with the value and the root. So the node starts off with the root node. If it's null, we'll just add the root.
>> Bianca Gandolfo: We just create a new node and we add it as a root here, cool?
>> Bianca Gandolfo: Of this tree. And remember, each tree is made up of sub-trees.

[00:02:14]
So each sub-tree has a root and two children, cool? So if we are inserting a number that is less than or equal to the value, actually just less than. Well, let's see. If it's equal to it, we don't wanna have duplicates in our binary search tree, okay? So if the value is less, the insert value is less than the current node's value, we wanna put it in the left tree, right?

[00:02:53]
So if it's null, that means there's a space for it. So then, we add it. Great, and then, we can return it at the end, just so that we have reference to it and we can do more things with it. Sure?
>> Speaker 2: So when we are checking for equal to, right?

[00:03:10]
>> Bianca Gandolfo: Yeah, I think it should just be this, yeah. Is that what you were gonna ask?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Yeah, cool. Otherwise, we're gonna call this again with the node dot left. So if it's not null, that means there's a left child there, and so we need to figure what that is.

[00:03:31]
So we'll go to the left node, and then we'll pass the value as well, the same value that we are looking for. Or that we're inserting, I should say. So if node dot left is null, it's not gonna be null, right? Because we already had that check here, remember?

[00:03:49]
So if it was null, we would have inserted it and returned. So we know that it's not null.
>> Bianca Gandolfo: So if the value is less than the current node's value, then we go into this block. Again, we check if
>> Bianca Gandolfo: There's nothing in its left place. Otherwise, we call it again, etc.,etc.

[00:04:18]
And similarly,
>> Bianca Gandolfo: If it's greater than, we enter into this else block.
>> Bianca Gandolfo: And this might be better as an else if value is greater than node dot value. Because I don't wanna overwrite or anything like that if it's a duplicate value. The specifics of your implementation is up to you, but that's how I like to do it.

[00:04:50]
And it really matters what you're doing it for. So again, it's the same thing for the right as well. And so, as you can see, at every level, it's gonna check left and right until it finally inserts itself into the right place.
>> Bianca Gandolfo: Any questions?
>> Bianca Gandolfo: Was this surprising?

[00:05:15]
Did you guys get this one?
>> Bianca Gandolfo: No?
>> Bianca Gandolfo: It's been a long day, I understand, all right.
>> Bianca Gandolfo: But does that make sense?
>> Bianca Gandolfo: Would you say that this is harder, easier, or the same difficulty as like a depth first or a breadth first search, for you, individually?

[00:05:44]
>> Speaker 2: A bit harder.
>> Bianca Gandolfo: A little bit harder?
>> Speaker 2: Having a helper function that is recursive is a bit more complex.
>> Bianca Gandolfo: You think? Interesting, so I would think that the helper function makes it easier.
>> Speaker 2: It does make it easier, I just wouldn't have gotten it.
>> Bianca Gandolfo: Okay, got it.

[00:06:01]
>> Bianca Gandolfo: Very cool.
>> Bianca Gandolfo: What about you, Michael?
>> Speaker 2: I didn't do the insert part.
>> Bianca Gandolfo: Okay.
>> Speaker 2: I kinda cheated. I already had an array. And then, I did the search part.
>> Bianca Gandolfo: Okay, okay, got it. The way I like to break down these problems is I just think about what if this is a tree with a parent and two children, right?

[00:06:21]
Like we did it earlier with the binary tree. For me, it's easier to start with that and then build on the recursive elements. Because maybe initially I wouldn't have started with this helper. I would have just started with these if else's and then said insert, which is essentially the same.

[00:06:46]
>> Bianca Gandolfo: The helper just kind of separates it a little bit.
>> Bianca Gandolfo: And it can be easier to reason about recursion when you're calling a helper function sometimes. I don't know, different strokes. All right, who's ready for contains? Did anyone try a contains?
>> Bianca Gandolfo: Okay, a couple people did contains.

[00:07:11]
>> Bianca Gandolfo: Very nice, all right, so we also have a helper here. So we will call it first with the root node. So if the node is null, we will return false, right? So that's sort of like the base for our recursion.
>> Bianca Gandolfo: And first thing we're gonna check is if the current node's value is value, then we're gonna return true.

[00:07:35]
We're all happy. Otherwise, if the value is less than the current node's value,
>> Bianca Gandolfo: And the left node is not null, then we're gonna recurse.
>> Bianca Gandolfo: And we're gonna come in here
>> Bianca Gandolfo: And keep repeating. Similarly,
>> Bianca Gandolfo: We'll check the right. And so, this is really similar from the contains before.

[00:08:09]
Except that when we're calling the recursion, we're either calling the left or the right. Versus before, we were calling out everything.