Alright, now that we know how to insert elements into a binary search tree, we might also want to remove elements from a binary search tree. And this is slightly more complicated, but I'm going to make it very simple for you guys. So when removing elements from binary search Street, you can think of it as a two step process. First, we have to find the element we wish to remove within the binary search tree, if it exists at all. And in the second stage, we want to replace the node we're removing with its successor, if one exists in order to maintain the binary search tree and variant, let me remind you with a binary search tree invariant is it's that the left subtree has smaller elements than the current node and the right subtree has larger elements than the current node. Okay, so let's dive into phase one.

The fine phase. So if we're searching for an element inside our binary search tree, one of four things is going to happen. The first thing is we hit a null node, meaning we've went all the way down our binary search tree and have not found the value we want. So the value does not exist inside our binary search tree. Another thing that can happen is the competitor value is equal to zero. And what I mean by competitor is, it's a function that will return minus one if it's less than zero if it's equal to, or one if it's greater than the current value.

So it tells us essentially, which subtree we need to go down or if we found value that we're looking for. So if it's equal to zero, then we found the value. If it's less than zero, the value might exist. And if it does, Soon to be in the left subtree. If I compare the returns value greater than zero, then if the value exists is soon to be in the right subtree. Okay, let's have a example with some animation.

So suppose we have four fine queries, fine, 1425 37 and 70. And that's our binary search tree there on the right. So if we're trying to find 14, as usual, we need to start at the root and 14 is less than so go left. 14 is greater than 10. So go right or teen is less than 15. Go left.

14 Is greater than 12. So go right again. And now we have found the value that we are looking for. All right, move on to 2525 is greater than 20. Go rate Wi Fi is less than 31. And now we find 25 See if you can do 37 on your own.

Pause the video or something. Okay, here's how go go right, your right, your left your right. All right, now let's have a look at 17th. So 17 should be on the left, now should go right. And we should go right again. And, oh, we've hit a point where we know that 17 does not exist in our tree.

So that's another possibility, the value simply doesn't exist. Because we would go to the left of 19. And the left of 19 is a null note, and no unknown means we haven't found the value we're looking for. So now that we found the value that we're looking for, we're at the Remove face and in the Remove phase, there are four cases essentially and the first case case is that the nobody wants to remove is a leaf node, so it has no sub trees. Cases two and three is like to call them is there's only one subtree. meaning there's a right subtree, but no left subtree or there's a left subtree and no, right subtree.

Or Finally, case four is that we have both a left and a right subtree. So I'm going to show you guys how to handle each of these cases, it's really, really not that hard. So case one, we have a leaf node. So if you have a leaf node and you want to remove it, then you can do so without a side effect, which is really nice. So suppose we have the binary search tree on the right, and we want to remove eight. So we do phase one, we find out where eight is.

Oh, and eight is a case one, because it's a leaf node. So We know we can remove it without side effect. So we remove it. Perfect. That wasn't hard. Now let's look at cases two and three, meaning that either the left or the right child is a subtree.

In this case, the successor of the node we're trying to remove is going to be the root node of that left or right subtree. Let's look at an example. Suppose we want to remove nine. So first, let's find nine. Okay, we found nine. Now we encounter a case two with a left subtree because nine doesn't have a right subtree.

So the successor is going to be the root node of that left subtree. So seven, so now we can remove nine and seven becomes the successor of nine. Perfect. Now let's do another example where we want to remove four. So first let's find four. So we find four.

And this is our other case where we only have a left subtree. But no right subtree. So when do we do? The successor of four is going to be the root node of that left? subtree. So three, so we can remove four and now three becomes the successor.

Alright, that wasn't so bad was it? Alright, so now for keys for now we want to remove node which has both a left subtree and a right subtree. Now the question is, in which subtree will the successor of the node we're trying to remove D And the answer is both the successor can either be the largest value in the left subtree or the smallest value in the right subtree. And here's perhaps some justification for why there can be two successors. So the largest value that we can find in that left subtree would satisfy the binary search tree invariant, if in terms of successor because it would be larger than everything in the left subtree and this is immediate from being the largest and left subtree and also it will be smaller, and everything in the right subtree because we've found it in the left subtree. Similarly, if we find the smallest value in the right subtree It would also satisfy the binary search tree invariant for the following reason it would be smaller than everything in the right subtree and this is immediate from being the smallest thing right subtree and also larger than everything in the left subtree because it was found in the right subtree and we know things in the right subtree are well greater than everything in the left subtree so we come to this conclusion that, well, there must be two possible successors.

So we can choose either or. Fantastic. So if we have this tree, and we want to remove seven, well, seven is a case for because it has both a left subtree and the right subtree. So seven, so find seven who've already found it. And now we get to either pick the successor in our left subtree or our right subtree I'm going to find the smallest value in the right subtree what we do We go into the right subtree. And then we dig as far left as possible, go left and go left again.

And now we don't have a left child, so we could stop and this node is going to be the successor is the smallest node in the right subtree. And you can see that quite clearly 11 is smaller and everything in that right subtree. So now what we want to do is, we want to copy the value from the node we found in that right subtree 11 into the node we wanted to originally remove, which is seven. So now I replaced seven with 11. Now we have a problem, which is we have 11 twice in our subtree and we want to now remove that element 11 which is highlighted because It is the successor it shouldn't no longer be inside the tree. And luckily for us, the successor node we want to remove is always going to be either a case one, two or three removal.

So in this case, it would be the case where there's a right subtree but now, left subtree and you would just do this recursively. So, so it would just call itself and it would hit one of those three cases. Okay, so it's a right subtree. So I want to do is swap it with the root node of that right subtree and then remove it. So remove 1114 becomes a successor. And now just going to rebalance the tree like that.

All right, now let's have a look at another case. In this example, let's remove 14. So first, let's find 14. If it exists within our tree, go rate. All right, we found 14. Now we either want to find the smallest value in the right subtree like we did last time, or the largest value in left subtree.

Now let's do the latter this time and find the largest value in the left subtree. To do this, what we would do is we would go into the left subtree and dig as far right as possible this time, go into the left subtree in Degas far right 913. Now 13 is the largest value in the left subtree. And now what we want to do as per before, is we want to copy the value of the successor 13 into the node we want to remove, which is 14. So now 14 comes 13 and now we Want to remove the remaining 13? So now just remove it and replace it with its successor.

Perfect. Okay, I just want to go over some more examples. So just these two short examples, because removing is not quite so obvious. All right, let's start the one with the left. So let's see if we can remove 18 from this strange looking binary search tree. So start at the root find 18.

So dig all the way down. Okay, we found 18. And now we want to, it's going to be it's one of those case two or threes. It's the one where there's a left subtree. So the successor is just going to be the root node of that left subtree or 17. So remove 18 and replace it 17.

So 17 is the new successor. Perfect. Now let's look at the other case where we want to remove minus two So now first find minus two. So go left. Okay, we find it found it. Now there's two subtrees, pick one of the two to become, to find it successor, I'm going to go to the right.

All right copies value in and I remove one, remove minus one. And that's it. Okay, and that is removals in a nutshell. So if you have any questions about removals or I went too quickly on something, just drop a comment below, I'll try to get back to you. But otherwise, we're going to be looking at some tree traversals In the next video, they can actually be quite useful. So stay tuned for that.

And if you want some source code for binary search tree removals, go look on my GitHub repository I have some source code which shows exactly how to remove elements from a binary search tree but Also be going over that source code at the end of the video series. So stay tuned guys, thanks so much for watching. Catch you next time.