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 "BST Search Procedure" 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:

A major part of a Binary Search Tree's insert() method is the search procedure. The insert() method must determine the property place for the inserted value. Bianca diagrams the BST search procedure by looking at the resulting tree after as different values are added.

Get Unlimited Access Now

Transcript from the "BST Search Procedure" Lesson

>> Bianca Gandolfo: Should we try this out? Should we do our stack trace thing that we do?
>> Bianca Gandolfo: Come on. Okay.
>> Bianca Gandolfo: All right, and just should have this automatically be JavaScript. Okay, this is all of our pseudocode.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Actually we can have it all, we'll undo, never mind.

[00:00:39] Here we go. Are you ready? So let's just say that we're gonna say, we're gonna call it BST and we're gonna pass it, this is our constructor. We'll just pass it 11, okay?
>> Bianca Gandolfo: And then we're gonna say BST.insert
>> Bianca Gandolfo: This is kind of like some quick and dirty sort of pseudo code, if that makes any sense to you.

[00:01:13] So we can insert 15.
>> Bianca Gandolfo: We can say insert 7.
>> Bianca Gandolfo: Okay, we're doing some inserts and we're gonna trace this through and see what happens, okay? So the first one is our constructor.
>> Bianca Gandolfo: Maybe we'll have two next to each other.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So we're gonna have our constructor, right?

[00:01:59] So we have our value, is what?
>> Bianca Gandolfo: 11, yeah, then we have left which is probably null, right, null. Yeah, cool. So now we're gonna insert 15. What we want it to look like, you want it to look like this.
>> Bianca Gandolfo: All right, and you know that this is gonna be a full object, but I'm just shorthanding it there.

[00:02:35] It's gonna be full object with a left and a right. Cool, so here we go.
>> Bianca Gandolfo: So in our insert, we're calling insert, our value is 15,
>> Bianca Gandolfo: And our current is what?
>> Speaker 2: 11.
>> Bianca Gandolfo: 11. So maybe that's something right, that we need.
>> Bianca Gandolfo: Right?
>> Bianca Gandolfo: Or maybe it's the stop-value.

[00:03:06] You need to access your current somehow. You get to choose how to do that. So we'll start out at 11. So is it less than 11? No. So we skip this. Is it greater? Yes. Is there a right?
>> Speaker 2: No, not yet.
>> Bianca Gandolfo: Not yet, so we're gonna insert.

>> Bianca Gandolfo: What does that mean, exactly?
>> Speaker 2: Create a new tree with the value of,
>> Speaker 2: Whatever it was, 15 in this case.
>> Bianca Gandolfo: And then what?
>> Speaker 2: And then return that tree.
>> Bianca Gandolfo: Return it?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Anyone have thoughts on this?
>> Speaker 2: When said new tree with value to the right side.

>> Bianca Gandolfo: Yeah, we want to add it to the right.
>> Bianca Gandolfo: So we probably wanna return it eventually, but-
>> Bianca Gandolfo: Normally indentation is messed up. It's driving me crazy. So we're gonna insert it, and we're gonna add it to the right.
>> Bianca Gandolfo: Current's right. Cool, so depending on how you're referencing current, it's gonna be something.right.

[00:04:43] Cool, maybe return. Great. So that worked. Good job. Our pseudo code is up to snuff. That's good news. So here is our tree you wanna insert 7. Where do we want this to go?
>> Speaker 2: It's gonna go to the left.
>> Bianca Gandolfo: And we're gonna put it here, right?

>> Speaker 2: Yeah the top level left.
>> Bianca Gandolfo: Okay, and again, this is short hand, this is gonna be a full tree. So let's check it out.
>> Bianca Gandolfo: So this returns, we pop it off, we're done.
>> Bianca Gandolfo: So our value is what? 7? Is it less than 11 which is our current?

>> Speaker 3: Yes.
>> Bianca Gandolfo: Yep, so is there a left?
>> Speaker 3: No.
>> Bianca Gandolfo: Nope. So we're gonna insert. We already talked about insert. We need to create a new tree and we need to add it to the current right.
>> Bianca Gandolfo: Cool, or left. Yeah.
>> Bianca Gandolfo: Great, so we did that.

[00:06:06] Success.
>> Bianca Gandolfo: So now let's try this one.
>> Bianca Gandolfo: Where should the 5 go?
>> Speaker 2: it will go to the left on the left again.
>> Bianca Gandolfo: To the left of 7, right?
>> Speaker 2: Left of 7.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: My short hand making sense. Yeah, I'll just type it out why not?

[00:06:42] So here is 7, it has a left, it does not have a right. All right, so right is null.
>> Bianca Gandolfo: Great. All right, so let's see how that works. 5, so is five 5 less than 11?
>> Speaker 3: Yes.
>> Bianca Gandolfo: Yes.
>> Bianca Gandolfo: Does 11 have a left?
>> Bianca Gandolfo: Yes.

[00:07:13] Yes. So then it says here, go left. What does that mean, exactly? How do we make it go left?
>> Speaker 2: You have to change, [COUGH] you have to make the current.
>> Bianca Gandolfo: This.left- Yeah. What he said, that's okay.
>> Speaker 4: This.left.insert the value.
>> Bianca Gandolfo: So this is a recursive call.

[00:07:40] Next one.
>> Bianca Gandolfo: Yeah? So this.left, so this is our current, right?
>> Bianca Gandolfo: Right, so we can just know that anything to the left of this dot is gonna be this in that function call, so this.left.insert what?
>> Bianca Gandolfo: The value.
>> Speaker 2: The value, right, which is 5.
>> Bianca Gandolfo: So then-

>> Bianca Gandolfo: The recursive side.
>> Bianca Gandolfo: Oops, what is the value, 5? And what is current?
>> Speaker 4: 7, maybe?
>> Bianca Gandolfo: 7.
>> Speaker 4: Okay.
>> Bianca Gandolfo: Yeah, what's your question?
>> Speaker 4: I think it clarifies here now.
>> Bianca Gandolfo: Yeah, yeah, so what we did is so we are gonna go left which is once we are at 7.

[00:08:50] So we're here, we are at 11 really and then we check left, we say is there a left? Yes. If there is a left, we wanna go to the next left. And so we just recursively call the function again. And we say this.insert on this node, left. So now this-

>> Bianca Gandolfo: Is 7.
>> Speaker 4: Because- So that shifted 7, right?
>> Bianca Gandolfo: Yeah, this is going to be the 7 node. The reason, we need to think about whatever, so the key word this is to find whenever you call a function. So before you call a function there's no value.

[00:09:35] And one of the ways to define it is by whatever this statement evaluates to and we just call it whatever is left of the dot at call time. That's how we say it at Hackreactor. So whatever this evaluates to, which this.left here when this is talking to 11, talking about 11 is gonna be 7, the 7 node, it's a node, right?

[00:10:03] So this is-
>> Bianca Gandolfo: This left, etc.
>> Bianca Gandolfo: Now, we're inserting there. So, that's the equivalent.
>> Bianca Gandolfo: And that's how we're drilling deep into our tree.
>> Bianca Gandolfo: So now we're in a layer lower, we're inside 7, so the current is 7.
>> Bianca Gandolfo: So is 5 less than 7?
>> Speaker 2: Yes.

>> Bianca Gandolfo: Yes. I'm so good at math. So and is there a left? Does 7 have a left?
>> Bianca Gandolfo: No, so what do we do?
>> Speaker 4: We set on current's left.
>> Bianca Gandolfo: Yep, there you go. So that's insert in a nutshell.