Data Structures and Algorithms in JavaScript

# Exercise: Deleting Two Children

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 "Exercise: Deleting Two Children" 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:

## In this exercise, you will complete the third case for deleting a node from a Binary Search Tree. The third case involves deleting a node that has two children.

Get Unlimited Access Now

Transcript from the "Exercise: Deleting Two Children" Lesson

[00:00:00]
>> Bianca Gandolfo: All right, so we practiced a little bit with the first two cases when we did the min max and we did it again for just more generic. So case three is, if we wanted to delete 2 here from our tree. What we want to do is find the minimum of the right tree, right, which is 4, and swap it with a deletion.

[00:00:25] So afterwards, you want the 4 to be in place of where the 2 was.
>> Bianca Gandolfo: Yeah.
>> Student 1: That's weird.
>> Bianca Gandolfo: Cool, want me to say it one more time?
>> Bianca Gandolfo: So, when we're deleting a note in a middle and it has two children, whether or not it has subtrees or whatever, it doesn't matter.

[00:00:57] You wanna find the minimum of the right subtree, and swap it,
>> Bianca Gandolfo: With the to be deleted.
>> Student 1: That will always work, because values on the right will always be bigger than values on the left.
>> Bianca Gandolfo: Yeah, so all of these.
>> Student 1: Yeah.
>> Bianca Gandolfo: All of these are gonna be less than 6.

[00:01:22]
>> Student 1: Yes.
>> Bianca Gandolfo: And then since 4 is less than 5, it's still meeting our requirement.
>> Student 1: Yes, okay.
>> Bianca Gandolfo: Yeah.
>> Student 1: Witchcraft.
>> Bianca Gandolfo: Yeah. So something to think about, again, is what if we deleted 6? And that's something to think about.
>> Bianca Gandolfo: Cool, any questions before we dive into the code?

[00:01:54]
>> Student 1: So the, cuz if we delete 6, we can't do the thing we were doing on the left cuz there is no min. No, there'd still be a min. You just wanted us to think about that, not talk about it?
>> Bianca Gandolfo: Well, it's something you're going to have to account for in all of your code.

[00:02:18] And we're gonna go through the solution for it, but I want you to come up with it on your own, basically, before I tell you. But just think about it. Think about the edge cases whenever you're creating your,
>> Bianca Gandolfo: Your data structures and algorithms, right? It's just good practice to try to predict what edge cases might arise that you might need to account for.

[00:02:42] Cuz it's useful to show, if you're in an interview, it's useful to show your interviewer, I'm thinking about the big picture here. I'm not tunnel visioned. I'm an engineer who is thoughtful and intentional about my code and considers edge cases. And there are more edge cases beyond this, right?

[00:02:58] There's the traditional edge cases, like what if it's empty or what if It's null? Some stuff like that. Cool? All right, well, I think you know what to do. You might want to pair, pseudocode it out, maybe you want to finish the other exercises first, so deleting the 1 and the 2.

[00:03:26] I'm sorry, the 0 and the 1. Before moving on to the second one so that you make sure you can test your code.
>> Student 1: Should these be different methods or one awesome method that does all the things?
>> Bianca Gandolfo: I like to have different methods just to break it out, but,

[00:03:50]
>> Student 1: Chef's choice.
>> Bianca Gandolfo: Exactly, there was one more thing I wanted to say about this. Yeah, it might be useful. Actually, before we do this let's implement a validation method that's gonna validate. It's going to, you call it on your tree and it returns true if it's a valid binary search tree, and returns false if not.

[00:04:22] And this will help you as you're building all this, to make sure that you're doing your swaps correctly. So it's just a way to make testing easier, cool?
>> Student 1: Okay.
>> Bianca Gandolfo: Great, any questions? So and that's also in the exercises, so if you go into the binary search tree exercises there is the is validate and it should be right before the delete node method.

[00:04:55] Not required but super helpful. It's also a very common interview question so it doesn't hurt to have that one in your tool belt.