Data Structures and Algorithms in JavaScript

# Binary Search Tree Exercise Solution

This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Binary Search Tree Exercise Solution" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca walks through the solution to the Binary Search Tree exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository.

Get Unlimited Access Now

Transcript from the "Binary Search Tree Exercise Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: So let's talk about our solution here, compare it also to our pseudocode, which I have at the bottom.
>> Bianca Gandolfo: Okay? So, here we are, first line, we are checking if the current value equals the value that's passed in. Okay. Next thing we're saying, if our passing value is less than the current value, what do we wanna do?

[00:00:32] Without looking at the code, what do we wanna do?
>> Speaker 2: Go left.
>> Bianca Gandolfo: We wanna go left. Cool. And here we are going left. We're catching this here with a double bang to stop it, if there is no left. So double bang, this is forcing it to a boolean true/false, so if this dot left is null, it's going to return false, which means that is not going to, go to the second side of end operator.

[00:01:08] So the logic behind the end operator, is that they both have to return true, in order for it to return true. Either one is false It's gonna return false, right, and operator. Except the way that it actually works is if the first one is false, it doesn't even go to run the second side.

[00:01:30] And so we use the and operator in this way as sort of a gate.
>> Bianca Gandolfo: Cool, and we also use the OR operator as sort of a default. We did that previously where We say if something is undefined you say or the default with the or operator. So that's just another one of those.

[00:01:54] Cool. Returning out from our aversion as well cool, then if the value is greater than the current value, same thing. If it doesn't exist, we'll return false.
>> Bianca Gandolfo: Or,
>> Bianca Gandolfo: Return whatever this returns, right. If it, maybe it's true somewhere under there.
>> Bianca Gandolfo: Cool? Then if we go through all that business,

[00:02:36]
>> Speaker 3: It's unreachable, isn't it?
>> Speaker 4: Isn't unreachable
>> Bianca Gandolfo: [CROSSTALK] Probably, let's see.
>> Speaker 4: That's how mine is and it works.
>> Bianca Gandolfo: It works?
>> Speaker 3: I guess it could be a double equals, but not triple equals.
>> Bianca Gandolfo: Hm?
>> Speaker 3: I guess it could be double equals, but not triple equals.

[00:02:55]
>> Bianca Gandolfo: For the second line?
>> Bianca Gandolfo: What do you mean?
>> Speaker 2: He's saying you have to go into one of those two if conditions, either the equals, less than or greater than are all covered. So there shouldn't be any way to get down to the false.
>> Bianca Gandolfo: Right. But he's saying if line 2 could technically be false if it was double equals, but not triple.

[00:03:18]
>> Speaker 2: So is it?
>> Speaker 3: Yeah that's what I thought.
>> Bianca Gandolfo: Well we would hope not. But maybe this will just catch the cases in which we don't enter into any of those conditions. Which means it's not equal, it's not less than, and it's not greater than.
>> Speaker 4: Why didn't you, when you had the value less Then this value have the check to see if this dot left existed right in there.

[00:03:46] Instead of having the and return contains value. So, like, at the end of value less than this value, and then have your And this.left.
>> Bianca Gandolfo: Yeah, you could do that. But this will also return false for us if we want.
>> Speaker 4: But then that way I only have the one return the false.

[00:04:13]
>> Bianca Gandolfo: Yep, yeah, that makes sense. Yeah. So if you didn't have this return here, and you just checked here, then this would be more useful for us.
>> Bianca Gandolfo: Cool. Questions?
>> Speaker 4: Yep, a question online from Oscar. Why do you use Not this.right instead of just this.right.
>> Bianca Gandolfo: So the double bang is forced to a boolean, and it's just to be sure that it gets forced to a boolean.

[00:04:47]
>> Speaker 5: Will it return undefined?
>> Bianca Gandolfo: Yeah, it might return undefined. Which is okay, but they're just weird with JavaScript and the truthy and the falsy situation is a little bit fuzzy when we force it. It's just more of a double-check more than anything. It'll probably work just fine without it.

[00:05:07] But there's a chance that something weird could happen, so double bang. So this would make it opposite, so if this was true this would make it false, the double bang. If it's true it makes it true, yeah.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: This is again, just a general JavaScript question, but if you just did return this.left, it would actually return the object or whatever, right?

[00:05:39] Is it the and that makes it?
>> Speaker 3: Yeah.
>> Speaker 2: If you just did return this.left, and you didn't have the and this.left contains value, it would just return the object, right?
>> Bianca Gandolfo: So you're saying if we didn't have this.
>> Speaker 2: Yeah, or the double bang. Yeah that would-

[00:05:55]
>> Bianca Gandolfo: Yeah we return the object.
>> Speaker 2: Yeah you don't want it to return null, you want it to return false, I think that's the point.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Yeah so for most cases it will even if it is null, null evaluates to false usually.
>> Bianca Gandolfo: The valuation falls but it's not, yeah.

[00:06:16] Okay.
>> Speaker 2: Yeah. Those are just little details not the most important thing. So what do we think? Does it makes sense? Cool, anyone do it differently?
>> Speaker 2: More or less the same, cool.
>> Bianca Gandolfo: I omitted the first line, this.value = false, and I returned true at the end.

[00:06:40]
>> Speaker 2: Yeah, so you just flipped it, cool.
>> Bianca Gandolfo: They're about the same.
>> Speaker 2: Yeah,
>> Speaker 2: Any a-ha moments yet? Still digesting both the food and also contains. That stomach contains Thai food. Yum. Alright, so let's check out what we have to do. Here, insert. We haven't looked at this yet, right?

[00:07:10] Let's check it out. I'm going to put it in here so we have the pretty colors.
>> Bianca Gandolfo: One question before we move on, from Oscar. Is the time complexity O log n?
>> Speaker 2: In the average/best case, yes. Worst case, no.
>> Speaker 2: Good question, though. Cool, so insert we went through the pseudocode a moment ago, but let's just look at the real code.

[00:07:44] So if the value is less than or equal to the current value, and there is a left, then you want to insert on the current left. Yeah? The regressive call. Otherwise, you're gonna set it, right. If there's nothing there you're going to put a new node in the current nodes left.

[00:08:12] The other condition is if it's greater and there is a right. Then, you're gonna recurse to the current node's right.
>> Speaker 2: Otherwise, if there's no right, then that's where we want to be.
>> Speaker 2: And then, we call it a day, and we want to just return out at the end.

[00:08:35]
>> Bianca Gandolfo: So that's returning the pair end, right?
>> Speaker 2: Mm-hm.
>> Bianca Gandolfo: Okay. I understood it differently.
>> Speaker 2: Well, it depends on where you are in the recursive call, right? But at the end, it's going to return the entire tree. It's gonna return a reference to it. Because that's what this is at the very beginning.

[00:08:57]
>> Speaker 2: But as you do these recursive calls You're changing the value of this.
>> Speaker 2: So depending on when you land here, this could be different.
>> Bianca Gandolfo: But you aren't returning the recursive calls, you're only returning the top.
>> Speaker 2: No but just imagine a world where you did a recursive call, you didn't get into any of this, this got skipped.

[00:09:31]
>> Speaker 2: That's where the return would pop up.
>> Bianca Gandolfo: So will the BinarySearchTree being returned always be the one that you called insert on, or will it be one of the subtrees?
>> Speaker 2: Yeah, the very last one is definitely gonna be the top one to the route, whatever it started with

[00:09:59]
>> Bianca Gandolfo: So that's what you would get as a return value?
>> Speaker 2: So with this implementation, you could chain multiple inserts. So you could say my BST dot insert three dot insert five dot insert 132, or whatever.
>> Bianca Gandolfo: I was returning the SubTree and I didn't get the use case for it.

[00:10:26]
>> Speaker 2: Yeah. Yeah, for the most part, you're only going to be interested in this at the end. Yeah. But it's going to return.
>> Speaker 2: Every time you call the function, it's going to return but it's going to get kind of caught up in your recursion. It's going to get stuck in there until the very last call