Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Deleting Min/Max Nodes" 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 begins talking about how to delete nodes from a Binary Search Tree. The first deletion algorithm she wants to implement is deleting the min or max value. Deleting the min value involves moving left until the left is null. Then set the left pointer of the parent to null.

Get Unlimited Access Now

Transcript from the "Deleting Min/Max Nodes" Lesson

[00:00:00]
>> Bianca Gandolfo: So one thing we haven't done yet is deleting our nodes. We'll delete the min which is the same as delete the max. And then we'll start back up tomorrow. Cool. So this is the binary searchery.
>> Bianca Gandolfo: So this is deleting the minimum value or the maximum value.

[00:00:23] Is that clear? So our minimum value, you'd want to delete three. Or for the maximum 25. Pretty straightforward.
>> Bianca Gandolfo: So let's pseudo code this out. We have some steps here.
>> Speaker 2: I don't really understand the second step.
>> Speaker 3: Set its right to the left of the parent. You have to, if you break the tree, because you delete a node you have to glue it back together, right?

[00:00:59]
>> Speaker 2: But it's the min, It doesn't have any children, right?
>> Speaker 4: Right, but it's down the minimum on the tree, right? After you delete the three.
>> Bianca Gandolfo: So what could we do? I mean, we could literally just set this to null, right?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: So we could just do that.

[00:01:17]
>> Speaker 2: Yeah.
>> Bianca Gandolfo: So let's start the easy way.
>> Speaker 2: Okay.
>> Speaker 2: You're speaking my language.
>> Bianca Gandolfo: [LAUGH]
>> Bianca Gandolfo: Okay, here, I'll delete this so it's not as confusing.
>> Bianca Gandolfo: Okay, so-
>> Bianca Gandolfo: What's the first thing we need to do? Go left. So you wanna traverse left, right?
>> Bianca Gandolfo: So if there's left, you wanna traverse, why do I do that sometimes?

[00:02:06]
>> Bianca Gandolfo: Okay. If there's a left, traverse left. This is for the minimum right, the minimum's gonna be left left left.
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Then, what else do we have to think about?
>> Speaker 2: Once you can't go left anymore, you wanna delete, right?
>> Bianca Gandolfo: So delete-
>> Bianca Gandolfo: That node.

[00:02:51]
>> Bianca Gandolfo: Okay, how do we delete that node? What would that look like?
>> Speaker 2: Is that the parents left to null?
>> Bianca Gandolfo: Cool, what do you think?
>> Bianca Gandolfo: Should we try it?
>> Speaker 4: You want to set the parents left to the value of the right. Is that the right signal?

[00:03:25]
>> Bianca Gandolfo: I don't think we have to do that. We'll just add to null, and then it's not there anymore right? We're deleting the minimum.
>> Bianca Gandolfo: And we're good.
>> Bianca Gandolfo: Cool,
>> Bianca Gandolfo: So let's run it.
>> Bianca Gandolfo: Cool, and let's look at our tree while we're doing it.
>> Bianca Gandolfo: All right.

[00:04:03]
>> Bianca Gandolfo: Can you guys see that tree okay?
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So our first go round, val is 11, right? True?
>> Bianca Gandolfo: Yes, cool. So does 11 have a left?
>> Bianca Gandolfo: True.
>> Bianca Gandolfo: So then we traverse left.
>> Bianca Gandolfo: Okay, then we skip down. Our value in question is which one?

[00:04:47] Seven. Seven have a left? Seven have a left? True. Traverse left
>> Bianca Gandolfo: Okay, our value is what? 5, this has a left TRUE. You're gonna traverse.
>> Bianca Gandolfo: So val equals equals equals three, okay?
>> Bianca Gandolfo: Does it have a left?
>> Bianca Gandolfo: False.
>> Bianca Gandolfo: So we don't traverse left.
>> Bianca Gandolfo: And our next task is delete that node by setting parents left node to null.

[00:06:00]
>> Speaker 3: So my question is, are we gonna wreck the whole tree?
>> Bianca Gandolfo: Hm?
>> Speaker 3: Are we about the wreck the whole tree?
>> Speaker 2: How do we stop all of the deletes?
>> Speaker 3: It's going to keep executing the deletes as it goes back up.
>> Bianca Gandolfo: Well, let's explore what would actually happen before we jump to conclusions.

[00:06:21]
>> Bianca Gandolfo: So we need to delete that node by setting the parents left to null.
>> Speaker 2: So we're on three right now.
>> Bianca Gandolfo: So we're here.
>> Speaker 2: We would want.
>> Bianca Gandolfo: We need five's left to be null. That would be a way to delete it, right?
>> Bianca Gandolfo: So how do we access five?

[00:06:52]
>> Speaker 2: We're gonna need-
>> Speaker 5: Argument of the function?
>> Bianca Gandolfo: Hmm?
>> Speaker 5: To make it an argument of the function?
>> Bianca Gandolfo: Yeah, so you could pass it in every time. You could always pass a reference to the parent.
>> Bianca Gandolfo: So, how to get a reference to parent. So that's probably the easiest way.

[00:07:13] Pass it in. So let's just say we have val and then we have this.parent or something that gets passed in.
>> Speaker 6: A question.
>> Bianca Gandolfo: Mm-hm?
>> Speaker 6: On the minimum values three, why you delete five?
>> Bianca Gandolfo: From the minimum value, why would we delete five?
>> Speaker 6: Yeah, if we are going to find minimum, we are deleting the minimum value or the three?

[00:07:39]
>> Bianca Gandolfo: Yeah, you're deleting the minimum values of three.
>> Speaker 6: So why make, why we change, make the parent null?
>> Bianca Gandolfo: Well, we don't make the parents null, we make their left. So 5.left should then be null, so that it doesn't have a pointer to anything. And then the three will just be garbage collecting, that's what we want.

[00:08:06] So, let's say we're passing in a parent every time.
>> Bianca Gandolfo: Not really a lot of overhead there, that's pretty simple, right?
>> Bianca Gandolfo: Okay, so.
>> Bianca Gandolfo: Great. So then we would just say like this.parent.next equals null.
>> Speaker 2: Not left?
>> Bianca Gandolfo: Thank you.
>> Bianca Gandolfo: Cool, so we deleted it.
>> Bianca Gandolfo: Are we happy?

[00:08:43] So let's see how we return up. So we delete it.
>> Bianca Gandolfo: So you wanna just say if there is no left or something, right?
>> Speaker 7: Yeah.
>> Bianca Gandolfo: Okay.
>> Speaker 3: [LAUGH] Otherwise you would just wreck your whole tree.
>> Bianca Gandolfo: We'll see.
>> Speaker 3: Which would be kinda fun to try.

[00:09:15]
>> Group: [LAUGH]
>> Bianca Gandolfo: Trying to get it not turn yellow.
>> Bianca Gandolfo: Okay, so where were we? So I'll just put this back up here, all right?
>> Bianca Gandolfo: So we exit out of this, right? So we set it to null, three is gone.
>> Bianca Gandolfo: And then we pop out of this traverse left,

[00:09:51]
>> Bianca Gandolfo: And then we say, is there a left for five?
>> Speaker 6: No?
>> Bianca Gandolfo: No.
>> Speaker 9: [LAUGH]
>> Speaker 9: [LAUGH]
>> Bianca Gandolfo: So then you're gonna delete five, that's a problem right?
>> Speaker 9: Yeah.
>> Speaker 2: Yeah.
>> Speaker 9: [LAUGH]
>> Bianca Gandolfo: We want it to stop
>> Bianca Gandolfo: So what can we do to stop it?

[00:10:22] We just want it, once it gets to three, we want it to delete it and then move on. We don't want it to keep deleting, that doesn't make sense. Cuz then we're just gonna have a really messed up tree. Actually, our tree would be totally gone, it just like.

[00:10:34]
>> Speaker 3: Yeah that would be totally gone
>> Bianca Gandolfo: Forever.
>> Speaker 2: Could we, when we, after we, like, it, well.
>> Speaker 3: Actually, wouldn't the 15 tree remain? Sorry.
>> Speaker 3: Can you just set a flag or something?
>> Bianca Gandolfo: You could.
>> Speaker 3: I don't know if that's a good way to do it,

[00:11:00]
>> Bianca Gandolfo: What if we do it first?
>> Bianca Gandolfo: How does that change the order? Does that fix it for us?
>> Speaker 2: Yeah.
>> Speaker 3: Yeah, it does.
>> Bianca Gandolfo: Okay. Try that.
>> Group: [LAUGH]
>> Speaker 2: Seems really simple, but I don't think I would have thought of that. [LAUGH]
>> Speaker 3: [LAUGH] That's like all it is with recursion, though.

[00:11:25] It's like, well I can't do that much but I can change the order of the things that I'm executing.
>> Bianca Gandolfo: Yeah, so let's try this.
>> Speaker 3: Cuz my solution is gonna be like five lines long or whatever.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: But the order you execute changes a lot.

[00:11:44] What's happening?
>> Bianca Gandolfo: Okay, so, we're here. This is where we've been ending at the end every time. Great. So we enter in our value is three. Three doesn't have a left. You delete the parents, pointer to null. Form, is there a left? No, so I'll just return, we'll pop out.

[00:12:11] This has nothing left in the function at all, we pop out.
>> Bianca Gandolfo: Right, and we continue popping out.
>> [INAUDIBLE]
>> Bianca Gandolfo: Seems useful, right?
>> Bianca Gandolfo: Cool. So what about the case where our minimum has a child? So now we deleted three, but five is our new minimum.
>> Bianca Gandolfo: So we need to account for that.

[00:12:47] And I'm gonna end it there, so sleep on that.
>> [INAUDIBLE]
>> Bianca Gandolfo: Sleep on that.
>> [INAUDIBLE]
>> Bianca Gandolfo: And then sleep on what if you're deleting a random one in the middle, what might you be able to do, just have it fresh in your mind and we'll go over some.

[00:13:14]
>> Bianca Gandolfo: Cool. All right. Well, see you guys tomorrow at nine-ish.