All language subtitles for 14 - How to Delete a Node from a Binary Search Tree English

So far we've talked quite a bit about how to construct binary search trees how to search through them

how to traverse them and different facets like that.

Now what we're going to do is talk about one of the more challenging things in learning about how binary

search trees work and that's how to delete a node from the tree.

So the very first thing I'm going to do is show how it works when you delete the root node.

So we have a root node of 5.

So when we delete that we're gonna take 5 out.

But before we can do that we need to find what we're going to put in first.

And so when you take the root node out you traverse down the left hand side of the tree and you find

whatever the highest of value is.

So say Just so you can see that again if we want to take three out again or take the root node out again

take three hit delete.

You'll see that we go down and we swap it out with two.

And so two is now the root node.

So another one that we can show how how the tree would tend to get reordered is low key as you want

to make sure that you maintain the not the proper balance because this is a balancing tree.

Just make sure that you maintain all the correct properties of a binary search tree.

If we want to take 15 now

we're going to first find 15 that's the first part of the algorithm and then from there because it only

has one child you can just take it out and move the pointer right to whatever its child is.

That's a very easy delete.

Now if we want to delete nine this is going to be slightly more complex because you can see Nine has

a child and 14 as a child.

So when we say we want to take out nine we go down the tree find nine and then we swap it out with eight

because eight is greater than seven but it's less than 14.

So we are able to keep all of the same properties of a binary search tree.

The very easiest thing that you can do when removing an item from a tree is to remove one of the leaf

nodes so we could take 14.

We take 14 or we have to do is traverse down the tree find 14 and then simply remove it.

If you were doing this in code you'd have to remove the pointer from 8 to 14 but when you're just doing

it visually like this you essentially can just pop it right off.

So that's all you have to do.

I showed you how to remove the root node and you know that in order to do that you find whatever value

is highest on the left hand side.

You swap those values and then you point that value to these other nodes it becomes the parent and then

becomes a parent of both sides.

And that's when you need to swap out the root node when you want to delete an item that only has one

child.

You can simply remove it and point directly to that child.

And then if you want to delete a node that has two children you go down to the left hand side and you

swap places with that one and then that has a pointer to the next one and then the last if you want

to remove the leaf then you simply pop it off and that's all you have to do.

So please let me know if you have any questions.

If that doesn't make any sense to you the first time you see it watch the video over once or twice.

It took me a while to become familiar with how binary search tree deletions worked.

It's not the most intuitive thing in the very beginning but the more you see it happen and the more

you play around with it the more it makes sense.

So please let me know if you have any questions whatsoever in the comments section and I'll see in the

next video.