Data Structures and Algorithms in JavaScript

# Deleting BST Nodes Solution Part 1

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 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 begins walking through the solution to the Deleting BST Nodes exercise. In the first part, she checks to see if the node is a leaf or if it has one child.

Get Unlimited Access Now

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

[00:00:00]
>> Bianca Gandolfo: So we're gonna do some pseudocode for our delete node. Delete node. It's gonna take a value. What's the first thing we gotta do?
>> Speaker 2: We should see if the stop value is equal to the
>> Bianca Gandolfo: So, what's that in pseudocode? That sounds like code.
>> Speaker 2: sorry. See if this is the node to delete.

[00:00:28]
>> Bianca Gandolfo: So, basically, search for the node.
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Cool, and how we could do that is check if current value equals value, yeah? Cool, what's the next thing?
>> Bianca Gandolfo: So we're searching for the node, we're checking if it equals the value. So we have two paths that we can take here.

[00:01:08] A binary tree, if you will, of options. Either it's true, the current value is the value, or it's not. So what do we do in each of those cases?
>> Unknown Male Student: If it is, then that's the one we wanna delete.
>> Bianca Gandolfo: If so, maybe we'll just call delete on it.

[00:01:42] Like that and then we can put in different function.
>> Unknown Male Student: Okay.
>> Bianca Gandolfo: Or we can do search. We could just take it out, okay? Else what?
>> Unknown Male Student: Keep looking.
>> Bianca Gandolfo: Right, maybe a recursive call to this search function. Cool, all right. So that's one thing that we have to do.

[00:02:25] So let's write our delete function, takes a val. What's our edge case that we were discussing earlier?
>> Speaker 3: Trying to delete the parent or trying to delete a node with two children?
>> Bianca Gandolfo: The edge case was deleting the root.
>> Speaker 3: Yeah, sorry, that's what I meant. There is no parent root.

[00:02:55]
>> Bianca Gandolfo: So if it's a root, we have to do some other stuff. Else it's not the root. Then what do we do?
>> Speaker 4: If it's a leaf, then
>> Bianca Gandolfo: Check if it is a leaf. If so,-
>> Speaker 4: I guess my question is we need access to the parent still, right?

[00:03:27]
>> Bianca Gandolfo: Maybe.
>> Speaker 4: We do, so we need to be passing the parent.
>> Bianca Gandolfo: Cool, and also depends on,
>> Bianca Gandolfo: Yeah, let's just pass, that would be easier. So delete,
>> Bianca Gandolfo: And we'll say current.
>> Bianca Gandolfo: Right, so current is gonna be the parent.
>> Bianca Gandolfo: Yeah, okay. So we're gonna check if it's a leaf.

[00:04:03] If so, what do we do? Miranda do you know?
>> Bianca Gandolfo: You can pass if you don't.
>> Miranda: Yeah, let's pass, [INAUDIBLE] [LAUGH]
>> Bianca Gandolfo: Cool, no worries. Rosie?
>> Rosie: Pass.
>> Bianca Gandolfo: Pass, okay.
>> Bianca Gandolfo: Let's see, David.
>> David: Well I was coding I guess, I'm sorry.
>> Bianca Gandolfo: It's okay.
>> Unknown Male Student: If it's a leaf we can just delete it, right?

[00:04:42] We don't have to worry about the children's, cuz it doesn't have any?
>> Bianca Gandolfo: Yeah.
>> Unknown Female Student: But you have to figure out if it's to the right or to the left of the parent that you're removing the pointer from.
>> Bianca Gandolfo: So delete it. Some things to consider when we're deleting it is which pointer do we swap?

[00:05:06] Since, for this case it could be left or the right. For our min max, it was either always a left or is always the right, right? Cuz the minimum is always gonna be on the left, maximum is always gonna be on the right, cool.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: And then we,

[00:05:30]
>> Bianca Gandolfo: We actually just gonna make a null, right? We're not gonna be swapping at this point, cool. Okay, so check if it is a leaf. If it is, we're gonna delete it. Something to think about when we're implementing this is how do we know if it's the left or the right?

[00:05:50]
>> Unknown Female Student: You'd check the parents, children, basically, and see which one it's equal to.
>> Bianca Gandolfo: Yeah, so you could just check.
>> Bianca Gandolfo: So you could say,
>> Bianca Gandolfo: If the parent's left equals the value, then set that one, for example.
>> Unknown Male Student: Equals this, right?
>> Bianca Gandolfo: Hm?
>> Unknown Male Student: Equals this?
>> Unknown Female Student: Yeah, equals this.

[00:06:21]
>> Unknown Male Student: I used the pseudocode.
>> Unknown Female Student: I mean, you could either compare the parent's left value with the value, or the parent's left node and the node, right?
>> Bianca Gandolfo: You can't compare the nodes, So it has to be the value.
>> Unknown Female Student: Okay.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: Anything else?

[00:06:45]
>> Unknown Female Student: If it has one child.
>> Bianca Gandolfo: All right, so case one if it's the root. Sorry, case one if it's the leaf, right
>> Bianca Gandolfo: Just putting that so we know. Here's our case one. Great, all right.
>> Bianca Gandolfo: Case two.
>> Bianca Gandolfo: Has one node. Is a leaf, right? Is a elaf.

[00:07:33] Is a leaf, okay. So check if you know the current node has a left or a right.
>> Bianca Gandolfo: Then what do we do? Andy do you know?
>> Andy: So you've checked if it has a left or a right. Whichever one it does have. You wanna set that one.

[00:08:10] So if it has a left then,
>> Andy: You wanna set that to the parent's left side?
>> Bianca Gandolfo: We can look at the picture.
>> Bianca Gandolfo: Where is our picture here? So,
>> Bianca Gandolfo: Imagining there's no 25 here.
>> Unknown Male Student: Uh-huh.
>> Bianca Gandolfo: And we're gonna delete 20?
>> Unknown Male Student: Yeah.
>> Bianca Gandolfo: What we wanna do is have 18.

[00:08:40]
>> Unknown Male Student: Yes.
>> Bianca Gandolfo: Be to the right-.
>> Unknown Male Student: Of the parent.
>> Bianca Gandolfo: Of the parent, right?
>> Unknown Male Student: Yes.
>> Bianca Gandolfo: And does it have to do with actually the fact that 18 is on the left?
>> Unknown Male Student: No.
>> Unknown Female Student: It doesn't matter where 18 is, it matters where 20 is to [INAUDIBLE] 15.

[00:08:59]
>> Bianca Gandolfo: So if we didn't have 18,
>> Unknown Male Student: Yeah, we would still be setting the right of the parent.
>> Bianca Gandolfo: Yeah, got it.
>> Unknown Male Student: So did we have a step already where we found our current node's relationship to the parent?
>> Bianca Gandolfo: Let's see, I don't remember anymore.
>> Bianca Gandolfo: Where's our pseudocode?

[00:09:24] Okay, yeah, I know. We're checking if the current node is left or right, but we're not actually checking the parent's relationship.
>> Unknown Male Student: You may need to do that.
>> Bianca Gandolfo: Should we do that first?
>> Unknown Male Student: Yeah, probably.
>> Bianca Gandolfo: Like, here?
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: So.
>> Unknown Male Student: We could do that like above the switch, right?

[00:09:56] Somewhere, cuz we'll need that info in every case.
>> Bianca Gandolfo: Yeah,
>> Bianca Gandolfo: So maybe If it's not a root, right?
>> Unknown Male Student: Yeah.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, set relationship from parent, right?
>> Bianca Gandolfo: So we want to know if it was coming from the left or the right. Because it's gonna inform where our next node will be, right?

[00:10:34] And we can use that in this step for example.
>> Bianca Gandolfo: Cool, all right.
>> Bianca Gandolfo: So if it has a left,
>> Bianca Gandolfo: Then set the left to the
>> Unknown Male Student: Parent's relationship side or whatever you wanna call it.
>> Bianca Gandolfo: Parent's relationship to be deleted node.