Data Structures and Algorithms in JavaScript

# Pseudocoding Min/Max Deletion

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Pseudocoding Min/Max Deletion" 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 pseudocodes the deleteMin() method which deletes the minimum value of a Binary Search Tree. This method is passed the parent node to traverse. It moves left until the left pointer is null. Once the minimum value is reached, the parents left is set to null to delete the minimum node.

Get Unlimited Access Now

Transcript from the "Pseudocoding Min/Max Deletion" Lesson

[00:00:00]
>> Bianca Gandolfo: So let's pseudocode this real quick. Step one, go left until left is null.
>> Bianca Gandolfo: So we'll have our,
>> Bianca Gandolfo: Function here called deleteMin.
>> Bianca Gandolfo: Okay, so we go left until left is null, but what does that look like in code? This makes sense in English. We don't have a go left.

[00:00:37] We don't have an until, really.
>> Speaker 2: I looked in our code, was just if this.left go.
>> Bianca Gandolfo: Mm-hm. So if there's left recurse.
>> Bianca Gandolfo: Recurse where though? So part of the recursion step, right, is we need to break the problem into a smaller sub problem otherwise we have an infinite loop, right?

[00:01:15] So if we just say recurse, or what that really means is delete min. On the child. I would do that again.
>> Speaker 2: This.left.child delete min.
>> Bianca Gandolfo: Yep, so we'd call it on the child node and this is breaking our problem down into smaller pieces.
>> Bianca Gandolfo: Cool, great.
>> Bianca Gandolfo: Now what?

[00:01:54]
>> Bianca Gandolfo: So for the case where it was the three, and it was the leaf, a leaf meaning there's no children.
>> Speaker 3: Don't you have to do the step that modifies the tree before, I forget what it was.
>> Bianca Gandolfo: What do you wanna modify on the tree?
>> Speaker 3: If the tree has children setting changing the children to take the place of the deleted node.

[00:02:29]
>> Bianca Gandolfo: So that's if there is two children, right now we're just working on one.
>> Speaker 3: Okay.
>> Bianca Gandolfo: But yeah. We have to do something along those lines.
>> Speaker 2: I remember-
>> Bianca Gandolfo: Good check in. [CROSSTALK]
>> Speaker 2: I remember from yesterday, the delete whatever it is, has to be before the gibberish thing, that's how we stop it from-

[00:02:47]
>> Speaker 3: Deleting the whole tree.
>> Speaker 2: Deleting everything, yeah.
>> Bianca Gandolfo: Yeah, yeah, yeah, yeah. Yeah, that' s a good reminder, if we delete after our recursion, we're gonna delete the entire tree and it's just gonna explode. It'll be some infinite loop.
>> Speaker 2: So would it just be this.value equals this.right?

[00:03:11]
>> Bianca Gandolfo: So if this.value equals, so we wanna see when the child is a leaf. So how do we check to see if the child is a leaf?
>> Speaker 2: If it doesn't have-
>> Speaker 3: If it doesn't have children.
>> Bianca Gandolfo: So if this.left and this.right is null, right? Yeah.
>> Bianca Gandolfo: Then what do we wanna do?

[00:03:58]
>> Speaker 2: I'm confused cuz I thought we were on a case where it did have a child node.
>> Bianca Gandolfo: Well let's start from the beginning.
>> Speaker 3: Yeah, we're starting from the beginning.
>> Speaker 2: Okay cool.
>> Bianca Gandolfo: Just so we have all the pieces here.
>> Speaker 2: So if this.left, is that right?

[00:04:17]
>> Bianca Gandolfo: So there's no children. You guys are calling me out on my errors.
>> Speaker 2: This.value equals null?
>> Bianca Gandolfo: So what happens if we set a value inside of an object to null? This is a common mistake.
>> Speaker 2: So we don't wanna change the value-
>> Speaker 3: We don't wanna change the value, you want to change the pointer to that tree.

[00:04:41]
>> Bianca Gandolfo: Yep, yep, because even if the value is null.
>> Speaker 3: We don't care.
>> Bianca Gandolfo: It's still a node. The node will still exist. It's just instead of three, it's now null which is gonna screw us up.
>> Speaker 3: We need a pop back up.
>> Bianca Gandolfo: Mm-hm, so you could try popping back up but we did think of an easier way last time.

[00:05:03]
>> Speaker 3: You passed the parent.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Yeah.
>> Bianca Gandolfo: So we deleteMin and we can pass the parent.
>> Bianca Gandolfo: And then what do we do? So now we have reference to the parent, so then you set their left to nothing.
>> Speaker 3: Parent.left
>> Bianca Gandolfo: = null. Yeah, so this is removing that pointer, which makes the node available for garbage collection, deleting it.

[00:05:39] Cool, great.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: This is zero children, and then the other case that we have Is one child, right? We'll never have two childs just because that's for a minimum it wouldn't work, right? Cuz for it to be a minimum it can't have a left.
>> Speaker 3: Right.

[00:06:07]
>> Bianca Gandolfo: Cool, so for the case that it's 5,
>> Bianca Gandolfo: What do we do?
>> Speaker 3: You get the value, so you have to check if it has a right node.
>> Bianca Gandolfo: Make it bigger?
>> Speaker 3: If it doesn't have a left node, and as a right node.
>> Bianca Gandolfo: Okay, so if it has.

[00:06:37]
>> Bianca Gandolfo: Not this.left, and or or?
>> Speaker 3: And.
>> Bianca Gandolfo: Why is it and?
>> Speaker 3: Because, if it has a left node, it's not the minimum.
>> Bianca Gandolfo: Cool.
>> Speaker 3: Then you would set,
>> Speaker 3: The value of this one to its right node's value. So you would say this.value = this.right.value I think.

[00:07:09]
>> Bianca Gandolfo: So this.value?
>> Speaker 3: Yeah.
>> Bianca Gandolfo: So you're gonna change the value.
>> Speaker 2: It was the same thing I did, the parent.left, right?
>> Speaker 3: Or do you wanna actually just change the node? You wanna change the node, okay.
>> Bianca Gandolfo: So we're using just simple integers in this case, but you could imagine our data structure could be really complex.

[00:07:31]
>> Speaker 3: Right, so then, you would do parent.
>> Speaker 3: Is it left? parent.left = this.right.
>> Bianca Gandolfo: What say you?
>> Bianca Gandolfo: Beautiful people in this class
>> Speaker 2: For the last if, why can't we just say L's parent.left = this.right?
>> Speaker 2: I think I lost the clock.
>> Bianca Gandolfo: So you're saying?

[00:08:12]
>> Speaker 2: Then wouldn't that execute on all of them as it walks back up if it was just an else?
>> Bianca Gandolfo: So you're saying doing it after the recursion?
>> Speaker 2: Yeah, and changing it to an else, because I think what he said. But wouldn't that execute-
>> Speaker 3: Yeah, you wouldn't want it down there.

[00:08:36]
>> Bianca Gandolfo: Shall we run it?
>> Speaker 3: Yeah.
>> Bianca Gandolfo: Let's vote. Who thinks we should do a second if? Who thinks it's better to have an else?
>> Speaker 2: It didn't have an else if, I just said else.
>> Bianca Gandolfo: An else.
>> Speaker 2: Maybe I'm confused.
>> Speaker 3: Yeah, he said else.
>> Speaker 2: I just said else.

[00:08:52]
>> Bianca Gandolfo: Okay.
>> Speaker 3: I don't know what's going to happen with else. I'd just be afraid because if you do another if, then you're very clear about what you're expecting. In this specific case, do this, right? If there is no left-
>> Bianca Gandolfo: There is two if statements too that we should be mindful of.

[00:09:11]
>> Speaker 3: Right.
>> Bianca Gandolfo: So we have if there's a left, and this one says if there is no left.
>> Speaker 3: Yeah.
>> Speaker 2: So is that also on the second if? Well, I didn't have the first if either. I just had If this left then this left delete min else parent left equals this right.

[00:09:38]
>> Bianca Gandolfo: Okay, well, let's continue on our main train of thought.
>> Speaker 4: Tegan had a couple of comments in chat too.
>> Bianca Gandolfo: Sure.
>> Speaker 4: Her ideas.
>> Bianca Gandolfo: See, would it be this.left instead of not this.left?
>> Bianca Gandolfo: So for this if, we're imagining that it's a 5 with no 3, because 5 with no 3,

[00:10:05]
>> Bianca Gandolfo: Would be the minimum, right? So there wouldn't be a left, so we're saying if there is no left, but there is a right, then that's our minimum.
>> Bianca Gandolfo: So that's why we're saying no left.
>> Bianca Gandolfo: Cool, so what do you think? If there's no this.left, there is a this.right, we'll set the parent's left to the current right.