Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Reviewing the Min/Max Pseudocode Part 1" 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 reviews the min/max deletion pseudocode by walking through each step in the execution. She looks at a couple different scenarios to make sure the code accounts for any edge cases.

Get Unlimited Access Now

Transcript from the "Reviewing the Min/Max Pseudocode Part 1" Lesson

[00:00:00]
>> Bianca Gandolfo: Shall we run it? When we have a tree, let's just do our subtree here, so we have 7 and then we'd have 5, what was the other one? Maybe 8.
>> Bianca Gandolfo: And then we had, what did we have? 3 and then 6.
>> Bianca Gandolfo: Cool, you guys see our little tree there?

[00:00:35] So 7 is the parent of 5, then we have 3, and then we have 6.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: Here is our tree.
>> Bianca Gandolfo: So let's say deleteMin(). The first time we run it we're not gonna pass anything, right? We're just gonna say tree.deleteMin(). Something like that.
>> Bianca Gandolfo: So we are going to put this onto our stack.

[00:01:17]
>> Bianca Gandolfo: All right, here we go. So, we start with the root node, which is our 7. Does it enter here?
>> Speaker 2: No.
>> Bianca Gandolfo: Okay, so, no, it has a left, it has a right. What about this one?
>> Speaker 3: That doesn't work either [CROSSTALK].
>> Bianca Gandolfo: Nope, for it to work it would not have a left but have a right.

[00:01:59] That's what that says. Both of those conditions need to be true for it to enter into this condition.
>> Bianca Gandolfo: And then otherwise, if there is a left, which there is, right, our 5, then we're gonna traverse, great.
>> Bianca Gandolfo: And then our value is 5. We can also think of this as this dot value.

[00:02:26] Okay, so does it have a left?
>> Speaker 2: Yes.
>> Bianca Gandolfo: Yes, so, it has left so it skips this so then we traverse again. This time going again to the left, so we go to 3. So === 3.
>> Bianca Gandolfo: Okay, so does 3 have a left?
>> Speaker 2: Yep, no, no.

[00:02:57]
>> Bianca Gandolfo: No, so that's true, right? Not left is true, what about not right?
>> Speaker 2: Doesn't have a right either.
>> Bianca Gandolfo: True, we forgot to talk about passing the parent. So we're passing the parent, at this point is 5, parent.left is null. Cool, so,
>> Bianca Gandolfo: We set that null, which essentially makes it go bye bye.

[00:03:28] So now we're left with this tree, so anyway we come to the end, right? We pop all this off.
>> Bianca Gandolfo: Yeah, so we pop them all off and let's pretend we're doing it all over again. We call the deleteMin one more time. It's gonna do a lot of the same thing, but the tree looks a little bit different now, cuz we don't have the 3.

[00:03:50] So the first time we call it, the value's gonna be 7. And there is a left, so we recourse.
>> Bianca Gandolfo: The next value is 5.
>> Bianca Gandolfo: And does 5 have a left?
>> Speaker 2: No.
>> Bianca Gandolfo: Does 5 not have a right?
>> Speaker 2: It has a right.
>> Bianca Gandolfo: So this is not true, so we skip this one.

[00:04:17] So does it now have a left?
>> Speaker 2: Yep.
>> Bianca Gandolfo: Does it have a right?
>> Speaker 2: Yes.
>> Bianca Gandolfo: And then we set its parent, .left, to this .right. So the parent, being 7, so 7's left,
>> Bianca Gandolfo: Is gonna be set to. So this our this, right here.
>> Bianca Gandolfo: Our 5 is the this.right.

[00:04:46]
>> Bianca Gandolfo: Does that make sense?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Can someone tell me that one more time, what I just said, in your own words? What are we doing?
>> Speaker 2: Setting 5 to 6, right?
>> Bianca Gandolfo: Mm-hm, yep.
>> Speaker 3: Setting the parent's left to the 5's, right?
>> Bianca Gandolfo: Yeah, absolutely. So we're essentially switching these out.

[00:05:17]
>> Bianca Gandolfo: Something like that.
>> Speaker 3: Is that what we wanted to happen? Did we wanna keep deleting the mins or did we just wanna delete the one min?
>> Bianca Gandolfo: We just pretended that we called it twice.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah, just so we could look at both, making sure that our code is working how we want it to work, cool.

[00:05:33]
>> Speaker 3: I have a question.
>> Bianca Gandolfo: You have a question?
>> Speaker 3: Why do we remove 5? Just we have to delete the 5s?
>> Bianca Gandolfo: Because 5 is the minimum.
>> Bianca Gandolfo: So this function is just always going to delete the minimum, and before we deleted it in this tree the 5 was the minimum.

[00:05:51]
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: And so the challenge that we are faced with is okay, we had to delete the 5, but we also have to do something with the 6. Cuz we're not just deleting the entire subtree, we're just deleting the one node, right? If we were deleting the entire subtree, then we'd be good.

[00:06:11] We'd just break off that reference and move on with our life.
>> Bianca Gandolfo: Cool, so again, we just switched them. Or, essentially, we moved 6 up and then 5 is disconnected.
>> Bianca Gandolfo: And we're all happy. And we're preserving the rules of a binary search tree, right? We wanna make sure always the left of the 7 is less and the right of the 7 is greater.

[00:06:41] And that's why when we do these delete operations it's really important that we're mindful of which side we're moving up.
>> Bianca Gandolfo: To which side?
>> Speaker 3: I guess one question is, what if the minimum is the root? What if the minimum is the root? Well it doesn't have a parent and we're going to set parent left equals null, and we're gonna have trouble.

[00:07:11]
>> Bianca Gandolfo: Yeah, absolutely. So how can you catch that?
>> Speaker 3: You could add a condition for end this .parent or at end parent in the first one? So that wouldn't try to set parent out left if there wasn't a parent.
>> Bianca Gandolfo: Well, it's not this .parent, it's just a parent, the parent [INAUDIBLE]

[00:07:35]
>> Speaker 3: Yeah, but wouldn't-
>> Bianca Gandolfo: So we can do a guard operator here. Something like that. But then we'd have to account for the Ls, right? And the question is what do we do with that node? Do we just set itself to null, do we just not let you delete it?

[00:07:58] What do we think?
>> Speaker 3: Cuz you're calling this on the tree, right? So in that case, it would be like the tree deleting itself.
>> Bianca Gandolfo: No, it's not gone though.
>> Speaker 3: Well, you didn't say this .right's going to be this .right's .right. I mean, I think the right child is gonna become the new root, so you're going to have to copy that over.

[00:08:29]
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Also there's still a right, there's just not a-
>> Bianca Gandolfo: So you could.
>> Speaker 3: There could be.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: It couldn't have a right.
>> Bianca Gandolfo: It could if we had something like this.
>> Speaker 2: Yeah.
>> Speaker 3: You wanna say deleteMin?
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Oops, sorry.
>> Bianca Gandolfo: So this is still a binary search tree.

[00:08:50]
>> Speaker 2: It can have a left.
>> Bianca Gandolfo: Yeah, so we meet this condition, not left, at this point, right? And we have a right, so how do we switch this? Make sure you account for that in your solution and we'll come back.