Data Structures and Algorithms in JavaScript

# Deleting Two Children Solution

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 Two Children Solution" 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 walks through the solution to the Delete Two Children exercise. In the solution, a node with two children must have it's subtree searched for the smallest value. That value will be moved to the position of the deleted node.

Get Unlimited Access Now

Transcript from the "Deleting Two Children Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: So we're gonna jump into the meat of our solution for deleting a node from a binary search tree. So can I just see a show of hands of who was able to get the binary search tree validation function working? Okay, cool, about half. And then who was able to get cases for the leaf to work?

[00:00:27]
>> Bianca Gandolfo: Cool, one node?
>> Speaker 2: Our cases worked, just [LAUGH] [CROSSTALK]
>> Speaker 3: Yeah, we're trying to put them together.
>> Bianca Gandolfo: Two nodes?
>> Bianca Gandolfo: What about for the case where it's a root?
>> Speaker 3: We didn't get that.
>> Bianca Gandolfo: Okay, cool. Jen, did you account for the root? Do you have [CROSSTALK] yet?

[00:00:45]
>> Jen: I think I have root, but I don't have the other one. I have the parents. Eh, that's what I'm fighting.
>> Bianca Gandolfo: Fighting with your parents?
>> Jen: Yep.
>> Bianca Gandolfo: Typical, [LAUGH] just kidding. Okay, here we go. So if this is found, so this is assuming that we're gonna search through our binary search tree and find the value.

[00:01:13] So once it's found, we're gonna enter into this if statement. So the first thing you wanna do is you wanna figure out how many children there are.
>> Bianca Gandolfo: So we add if there's a child, then it's 1. If it's a child on the left, then add 1, otherwise 0.

[00:01:40] If there's a right add 1, otherwise add 0. Cool, so we have a tiernary operator with some addition. And it's literally just counting if there's 0, 1, or 2 children. Any questions about this, what's going on there?
>> Bianca Gandolfo: Can I get thumbs, we're good? Okay, so if the value is at the root, we're gonna enter into this.

[00:02:17] So we're gonna just do a switch statement,
>> Bianca Gandolfo: On how many children there are. So if there are 2, then we're going to set a replacement to the root's left. Okay, and then you wanna find the right-most leaf node, and it's gonna be the new root.
>> Bianca Gandolfo: Does that make sense?

[00:02:44]
>> Bianca Gandolfo: So.
>> Bianca Gandolfo: So we're gonna keep going right. So while replacement.right is not null, we're gonna keep incrementing. replacementParent is gonna be replacement. Cool, so there's us tracking that replacementParent, cool? So this is getting us to the right-most node in our binary search tree.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, so here is the case if it's not the first node on the left.

[00:03:37]
>> Bianca Gandolfo: Then we're gonna remove the new road [LAUGH], road, the new root from its previous position. So here we are putting the left's replacement onto the replacementParent's right.
>> Bianca Gandolfo: Then we're gonna give the new root all of the old root's children, right? And by all of them, we mean both.

[00:04:05]
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: Got any questions? So otherwise we'll just make our,
>> Bianca Gandolfo: Our assignment here. Actually, I'm lost at what this is doing. Replace right with this._root.right. Okay. So you're going to take the root's right and put it into its final position.
>> Bianca Gandolfo: And this._root is a replacement.

[00:04:43] So here's a way to get around the assigning this equals this, is if we give our tree data structure, our constructor, a root. Yeah, so just like we had a storage in our,
>> Bianca Gandolfo: In other data structures we've made, this implementation, and this is Nicholas Zakas' implementation, has a root in its constructor.

[00:05:09]
>> Bianca Gandolfo: So the other way of doing this is we would just assign it to the value instead of the entire node.
>> Bianca Gandolfo: Cool. So that's for the case where it's the root, right? Which is kind of a special case, a little more complicating.
>> Bianca Gandolfo: Right. So otherwise, there are two children, this is when remember we are going to take the left-most node of the right node.

[00:05:54]
>> Bianca Gandolfo: Did you guys get that?
>> Speaker 2: And then of the right.
>> Bianca Gandolfo: And I'll just show you the picture, so.
>> Speaker 3: Yeah. The left-most of the right and we replace it, so that's what we're doing here. Cool, so here's a replacement, current.left.
>> Bianca Gandolfo: This one's actually going the other way.

[00:06:19]
>> Bianca Gandolfo: current.left. So this one's just going the other way. So replacementParent is current.
>> Bianca Gandolfo: Here's our current.
>> Bianca Gandolfo: So and we're gonna find the right-most node instead of the left-most node. This is just an opposite implementation. If you wanna switch it, you just change left and right. So I'll go all the way, all the way, all the way to the right-most node.

[00:06:49] And the replacementParent,
>> Bianca Gandolfo: Is just gonna be the one right above that.
>> Bianca Gandolfo: Cool, and then we just swap them.
>> Bianca Gandolfo: Then we assign the children.
>> Bianca Gandolfo: And then you swap them. So instead of, how'd we do it in the pseudocode? We said something like we were just gonna keep track if it was on the left or the right or something like that, of the parent.

[00:07:21]
>> Speaker 2: Yeah, we were passing a parent relationship.
>> Bianca Gandolfo: Yeah, so what we could do is just compare the values instead. And we give the left the replacement or the right the replacement, depending on if the current value is bigger than the parent value, right? Cuz if it's bigger it goes on the right, if it's lesser, it goes on the left.

[00:07:46] And those are our cases, or that's the third case at least.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: Any questions? It's kind of a lot.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: That's deleting a node from a binary search tree.