Data Structures and Algorithms in JavaScript

# Deleting BST Nodes Solution Part 2

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 "Deleting BST Nodes Solution 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 the solution to the Deleting BST Nodes exercise. She finishes the pseudocode for deleting nodes with a single child. If the deleted node has a child, that child will be set to either the left or the right pointer of the parent. The location depends on the deleted node's relationship to the parent.

Get Unlimited Access Now

Transcript from the "Deleting BST Nodes Solution Part 2" Lesson

[00:00:00]
>> Bianca Gandolfo: So we check if the node has a left or a right, so just one or the other. If it has a left, then you're gonna set the left.
>> Bianca Gandolfo: We're gonna set the left.
>> Bianca Gandolfo: To the parent's relationship, right? So the parent
>> Bianca Gandolfo: Is to the right of the 15, right?

[00:00:25] So we want to, we're here, this is our current value. This is our this dot left, right. We wanted to change our this dot left to our parent dot right. Or whatever our parent's relationship is. Cool, so we could save that into a variable called position or something like that.

[00:00:49] And then just use bracket notation, say this bracket position equals this dot left. Does that make sense?
>> Bianca Gandolfo: Okay, if has a left, then set the left to the parent's relationship for the to-be-deleted node. It's really verbose, does anyone have a shorter way of saying that? In English though.

[00:01:22] I'm trying to make it more English than code.
>> Speaker 2: Look to the parent's relationship for it.
>> Speaker 3: We could just decide on an acronym and then remember what it means [LAUGH]
>> Bianca Gandolfo: So what about the PRD? That doesn't stand for anything bad, right?
>> Speaker 3: Not that I know of.

[00:01:46]
>> Bianca Gandolfo: Okay, me either. So parent's relationship to the deleted.
>> Speaker 3: Thank you.
>> Bianca Gandolfo: Okay. Cool.
>> Bianca Gandolfo: PRD.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: Did you look it up?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: No. [LAUGH]
>> Speaker 2: That was super funny.
>> Bianca Gandolfo: What about PRDN.
>> Speaker 2: It doesn't matter. PRD is fine. It's just funny what it actually stands for.

[00:02:20]
>> Bianca Gandolfo: Is it bad?
>> Speaker 2: PRDN actually doesn't have a reference.
>> Bianca Gandolfo: Okay.
>> Speaker 2: It's,like if you're a runner, pre-race dump.
>> Bianca Gandolfo: Yeah, we're gonna do PRDN. Just deciding. Okay, so PRDN, okay, so if it has a left then you're going to set the. Actually we're going to set the PRDN to this left It's easier.

[00:03:00]
>> Bianca Gandolfo: Cool? And that's how we're swapping it out. So, if right, then set PRDN to this.right.
>> Speaker 2: Is it if it has one, if it matches The value of that there?
>> Bianca Gandolfo: So.
>> Speaker 2: Right?
>> Bianca Gandolfo: So we already, so the current node is the match node. And so at this point we wanna say, you know, if it has a child then we wanna swap it.

[00:03:37] And we wanna just make sure that we're swapping it to the right place. So what you really could do, actually let me see, two this dot left or this dot right. Right assuming you are sending it to the value not the entire node. Because the node but actually either way it does not matter

[00:04:04]
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: What else are we missing?
>> Speaker 2: We were not suppose to do, for this too.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Cool. So, let's walk through. So if it's a root, we need to account for that, we talked about earlier. It's probably like three or six lines of code.

[00:04:43] To account for that, otherwise.
>> Bianca Gandolfo: We'll set up, who the parent is, right? So if it's not the route, it has a parent.
>> Bianca Gandolfo: And we're passing it.
>> Bianca Gandolfo: So the first thing is we wanna check if it's a leaf. If it is, you wanna delete it And so how we delete that is we set the PRDN to null, right.

[00:05:22] So that would look something like parent[right] = null.
>> Bianca Gandolfo: Does that make sense? What that means in code.
>> Bianca Gandolfo: Where this is a string.
>> Bianca Gandolfo: Cool, so the other case is if it has one known. We gonna check if it's a left or right, you know. This is actually where we're checking if there's one node.

[00:05:59] And then we're just gonna set it. So what that might look like is, parent ["right"] =
>> Bianca Gandolfo: One or the other. So if one of these is evaluating to true, it's going to save it. We know that one of them is true and one of them's false. And so that should work for what we're doing here.

[00:06:27] Cool, anything else? Who finished this in the three minutes? You can raise your hand if you did. Okay, all right. You ready for case three? Awesome. Any questions?
>> Speaker 3: What is case three?
>> Bianca Gandolfo: What do you think is case three? So case one it's a leaf, case two there's one node.

[00:06:55]
>> Speaker 3: I would think two nodes.
>> Bianca Gandolfo: Umhm. Yeah, that's our only other option. Case three is, what if there's aliens?
>> Speaker 3: [LAUGH]
>> Bianca Gandolfo: It's a real thing. Okay.
>> Bianca Gandolfo: So case three is, when the node has two children