Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Reviewing the Min/Max Pseudocode Part 2" 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 continues her review of the min/max deletion pseudocode. She checks the code against an edge case where BST nodes only have right children.

Get Unlimited Access Now

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

[00:00:00]
>> Bianca Gandolfo: So we're gonna talk about a couple edge cases that were brought up. How to account for them and then we're gonna look at a solution. And then we're gonna see if we can optimize our solution and then we'll keep rolling. Sound good? All right, so what David was talking about before we went and did our exercise, was what if our minimum is the root?

[00:00:24] And so there's two cases where the minimum is the root and then it has a right sub-tree. And then, what about the case when the minimum is the root and also the last element in the tree? Are there any other edge cases that come to mind, that came to mind when you were doing these exercises?

[00:00:53]
>> Bianca Gandolfo: Cool. All right. So, for this case, if we were to delete 7,
>> Bianca Gandolfo: What would we have to do to our tree? So I wrote out our tree just so we'd have a reference to what it looks like. Like, what would we have to change in this nested object for it to be correct?

[00:01:23]
>> Bianca Gandolfo: So we want.
>> Bianca Gandolfo: Sorry, that's not what we want. We want two lined up like this.
>> Student1: All the pointers aren't filled out.
>> Bianca Gandolfo: It's just the right pointers are, see?
>> Student2: Tree.
>> Student1: Which one has on the right tree, not just-
>> Bianca Gandolfo: There's no left.
>> Student1: Right.

[00:01:46]
>> Bianca Gandolfo: But the right is, this is the right.
>> Student1: So then the 8 one would be pointing to 9.
>> Student2: This is the parent.
>> Student1: I get it, I gotcha, yep.
>> Bianca Gandolfo: Actually this one would be null.
>> Bianca Gandolfo: Okay, so we have this tree on the left. Here it is as an object.

[00:02:21]
>> Bianca Gandolfo: What do we want it to look like after we run a delete method on it?
>> Student2: Just the second two lines.
>> Bianca Gandolfo: Yeah, so we would essentially delete.
>> Bianca Gandolfo: This top one, right? And we want it to look something like this.
>> Bianca Gandolfo: But how do we do that in code?

[00:02:44] We can't just delete. Can we?
>> Bianca Gandolfo: Not like that at least.
>> Student2: Yeah, we couldn't really figure out a way with our implementation. Because we don't really have the concept of a root other than it's the node that you start on.
>> Bianca Gandolfo: Mm hm.
>> Student2: And we couldn't figure out a way to.

[00:03:09]
>> Bianca Gandolfo: Yeah, so the root is just where it starts, which is going to be saved in the variable. So because it starts here, because the very first value in our object, let's save into our variable name. Has the value 7 or 7 is the root.
>> Bianca Gandolfo: So we'd want it to look like this, where our very first object in our nested data structure is, the 8.

[00:03:45]
>> Bianca Gandolfo: So essentially, what I recommend is to rewrite 7, 7s value to 8. Change its, overwrite its right value.
>> Bianca Gandolfo: To 8 dot right.
>> Bianca Gandolfo: That makes sense?
>> Student2: Yes.
>> Student1: You're just overwriting the value?
>> Bianca Gandolfo: Do you wanna over write both the value?
>> Student1: I thought we couldn't do that.

[00:04:20]
>> Bianca Gandolfo: And the right.
>> Student2: We tried to do that and we thought you couldn't do that for some reason. Something about the value being, where if in cases where the value is more complex or the node held more.
>> Bianca Gandolfo: Yeah, but in this case, do you have any other thoughts about how we could do it?

[00:04:37]
>> Student2: No.
>> Bianca Gandolfo: Anyone else?
>> Bianca Gandolfo: Me either. [LAUGH] Or I guess the other way you could do it is simply just reassign.
>> Bianca Gandolfo: Starting here, right? So if you said myBst = myBst, let's see, so we have to go to dot right, then we just assign it directly.

[00:05:16] Does that make sense? Any questions?
>> Student2: Can you do that from within? We tried setting this equal to this dot, right? In it, it wouldn't run. Can you, could we do it at three? If we had just done variable name equals variable name that would work.
>> Bianca Gandolfo: So, inside the function you probably want it to be this.

[00:05:46] And only for the case when it's the node, when it's the root node.
>> Student2: Okay, yeah, that-
>> Bianca Gandolfo: Yeah, that make sense?
>> Student2: We got an error when we tried doing that, it said-
>> Bianca Gandolfo: Just make sure-
>> Student2: Invalid left-hand side in assignment.
>> Bianca Gandolfo: Yeah, are you doing it on the prototype and everything?

[00:06:05]
>> Student2: Yes.
>> Bianca Gandolfo: Okay, I don't know.
>> Student2: The SQL stuff-
>> Bianca Gandolfo: I can look at your specific error.
>> Student1: Okay.
>> Bianca Gandolfo: Yeah, you can re-assign. Okay, questions, comments? Okay. So what about this? What do we do here? So we wanna delete the minimum, but we only have one value and because of that fact, it's also the root.

[00:06:42]
>> Student2: If we can re-ascend the value, we can just say the value equals null.
>> Bianca Gandolfo: Mm hm.
>> Student2: Or if this assignment works, we could just set so equal to null.
>> Bianca Gandolfo: So if we said this equals null, then it would look like this. Bst, like that. So both work.

[00:07:07] Just depends on what you want to do next with it, right? If you just want it to disappear and you're never going to touch it again? You know, it's reasonable to say it's a null. But if you're going to continue to add children to this? Leaves, notes, then you're going to want to make sure that you preserve the left and the right.

[00:07:27] So that you can continue growing it. So kill the tree forever, maybe you wanna use it later,
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Here's a quick and dirty deleteMin.
>> Bianca Gandolfo: So let's check it out.
>> Bianca Gandolfo: So, this is the deleteMin, by the way, not the deleteMax. So if there's no left and there's no right and there's a parent.

[00:08:09] We simply set the parent left to null, otherwise we delete the value, right? And this is for the case where we want to add nodes later, or whatever. It preserves the node tree structure, doesn't delete it forever, or forever, right? Sets it to null? Cool, make sense?
>> Bianca Gandolfo: Otherwise, if there isn't a left, but there is a right and there's a parent.

[00:08:46] We set the parent's left to its right. Otherwise we can reassign the value or just like we talked about a second ago we could also say this dot Ew, you're right, we can't set this to anything.
>> Student1: Yeah you can't.
>> Bianca Gandolfo: So we would be stuck doing.
>> Student1: That's what we were stuck on.

[00:09:13]
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Okay. I'm happy with that solution then. So, this the only way that you can assign this is using call and apply. That's when you can just like choose what you want this to be, but you have to do it when you're invoking the function. You can't just assign this willy nilly.

[00:09:42] You can assign properties to this, you could say like, this dot xyz, you could do that, but you can't override it. Cool. Yep, otherwise, we were gonna recurse.
>> Bianca Gandolfo: Cool? Quick and dirty, straightforward, very verbose.
>> Bianca Gandolfo: So what if we want it to just change this to delete max?

[00:10:07]
>> Bianca Gandolfo: What do we have to change?
>> Student2: Invert the lefts from the rights.
>> Bianca Gandolfo: Okay. Is that it?
>> Student2: Yeah I think so.
>> Bianca Gandolfo: Uh-oh.
>> Student2: Yeah [LAUGH] I was gonna say, wow! You have really good memory.
>> Bianca Gandolfo: I'm gonna forget it all. Okay.
>> Bianca Gandolfo: Okay, now I'm remembering.

[00:10:45]
>> Bianca Gandolfo: And you're gonna see how this.left.left works. It works because it's a nested tree.
>> Bianca Gandolfo: Double-check me here, folks.
>> Student1: Also, if not this and this, there you go.
>> Bianca Gandolfo: That's all.
>> Bianca Gandolfo: Cool. Run the code in your mind. So, if it has a right
>> Bianca Gandolfo: Where's our slides?

[00:11:25]
>> Bianca Gandolfo: Let's look at our picture. So let's say we're deleting 25. So we say if there's a right, we're gonna go all the way down right, right, right. So if there's no children, there's a parent, so we're setting to null. So leaf works great. So let's say we don't have 25 and we're doing 20.

[00:11:54] Pass it in, [SOUND] all the way through. It doesn't have a right and it has a left. It does have a parent. So we say parent dot right equals this dot left. Cool. Sounds good. Sure, question?
>> Student3: What is this value is equal to now do?
>> Bianca Gandolfo: You have to say that one more time and not have your hand in front of your mouth.

[00:12:19]
>> Student3: What's not in the else this.value is null. Yeah, what does it do?
>> Bianca Gandolfo: So this is if a, if the root, if the max value is the last node. So there's no more nodes in this tree. So we're just deleting this one node and imagining there's no other nodes here.

[00:12:48] So for a tree of size one, what do you do? You just set that value to null and it's just an empty tree at that point.
>> Student3: And then you can [INAUDIBLE] statement.
>> Bianca Gandolfo: Yeah, so this is for the case that there is, so this is for, let's see.

[00:13:13] So the max val is the root with a subtree.
>> Bianca Gandolfo: So, where is our, so this is the case that we're counting for. Where it's 7, 8, 9, this is the minimum example, but it's the same idea. So if we wanted to delete 7, it's the node, so we have to do something different, because the node doesn't have a parent.

[00:13:44] And so that's why we account for it in all these craziness nested if-else statements.
>> Bianca Gandolfo: And there are shorter ways to do this. This is the most verbose step by step.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: Awesome.
>> Bianca Gandolfo: Moving on.
>> Student3: Delete max.
>> Bianca Gandolfo: Hm?
>> Student3: How will you correct, if you forgot delete max.

[00:14:15]
>> Bianca Gandolfo: What's that?
>> Student3: The last statement, if, yeah delete max is.
>> Bianca Gandolfo: This one?
>> Student3: The last if.
>> Student2: Line 16, the delete min.
>> Bianca Gandolfo: Hmm, good eye.
>> Bianca Gandolfo: Very cool.
>> Student1: That would make for a confusing bug.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Yeah, especially if deleteMin also existed.
>> Bianca Gandolfo: All right, any questions?

[00:14:55]
>> Student2: Yeah, so for an empty tree, we're setting this value equals null. Does that mean we'd have to check for this value equals null in all of our other methods?
>> Bianca Gandolfo: Yeah, yep.
>> Bianca Gandolfo: Yep, so it depends. If you wanna account for an NP tree in your implementation, that's how you could do it.

[00:15:20]
>> Student2: Just making [INAUDIBLE] method.
>> Bianca Gandolfo: Hmm?
>> Student2: Probably just make them use empty method.
>> Bianca Gandolfo: Yep.
>> Student2: Insert that everywhere.
>> Bianca Gandolfo: Yeah. All right. Cool. So we talked about delete min/max. This is a simplified example of just deleting a node, more generally from a tree. So when we're deleting a node from a binary search tree, there's three cases and we already talked about the first two in our min and max, right.

[00:15:53] The first case is when a node is a leaf node. What do we do?
>> Bianca Gandolfo: What do we do if it's a leaf node, meaning it has no children?
>> Student1: We remove the pointer from the parent.
>> Bianca Gandolfo: Mm hm. If when into null, parents pointer is now null, that's pretty straightforward.

[00:16:14] And what do we do when the node has one child?
>> Student1: Move the node.
>> Bianca Gandolfo: Yep, you just move the node up to the parent. And we know that it's going to meet our requirements because the entire right sub-tree is always going to be greater than the root node.

[00:16:46] Or the node in question and the entire left sub-tree is going to be less. So if we move it up and it's just one node.
>> Bianca Gandolfo: Then we're good to go.