Hey guys, in this video I'm going to go over how to add and remove from binary search trees.
You can compare this to my last video that was similar but it was adding and removing from heaps.
I'm going to do these steps sequentially starting with add. Adding to a binary search tree is really simple.
I guess I should explain briefly, so binary search trees--
the parent node is always greater than all the values on the left subtree.
And it's always less than all the values on the right subtree. You can see that this is true for every node
that's considered a parent node. That was just a brief review. Adding is really simple and it's easier
I think than adding to heaps. You always just add a new leaf node to binary search trees.
You never have to push anything up into the tree, you just add a new leaf.
And you just want to make sure you're adding it to the correct position.
The first one we're going to do is 5. Five is less than
6, so it would be on the left subtree of 6. We add that leaf there
and we're done with that. Twenty-nine. Let's see here, 29 is greater than 27
but less than 32. We can add it there and we're done with that.
Thirty-three. So 33 is less than 49
but it's more than 32. Similarly we can add it there. Ten. Ten is already there.
In binary search trees, you do not add duplicates whereas in heaps you can. We're done with that
because 10 already is on the binary search tree. 28. Twenty-eight is
less than 29, but more than 27.
We add it as a new leaf there
and we are done with adding. And then removing basically has three cases.
You can remove just one leaf that has no children and all you have to do is remove that node.
That's one case. The second case is when
you're removing a node that has one child.
For example if we needed to remove 15, what you do in that case is you just bump up the one child to the
parent node's location.
If you're removing the parent node 15
you would just remove 15 and then
move up 13 to this location. And then the third case is when you remove a parent node that has two children.
For example if we had to remove 27, we can't just bump up one of these
Children nodes because we have to consider which one are we moving up.
There are two options with this third case. You can either bump up the largest
child in the left subtree, or the smallest child in the right subtree.
And this is because we want to get a value that's always going to be smaller [than] the right subtree
so the largest value in the left subtree will always be less than the right subtree and
The smallest value on the right subtree will always be larger than the left any value in the left subtree
So that's kind of the idea with that and we'll do these three [examples] to show you what I mean
so to remove six that has one child node only so we would just remove six and bump up the
Child leaf node and we're done with that to remove five five now has it's a leaf node, and it has zero children
So we could just remove five and we're done with that to remove ten so this has a child node with another child node
But it's the same thing as the case with [only] one child so the only thing you would do is bump this up and make
This 15 and then this would be 13
you're really just moving this whole branch up one and you can pretend that this is gone.
I should probably be rewriting this but hopefully you can see what's going on. And then the final case is going to be 32.
32 is the case where you have to consider two
child nodes. In my case, I think I will just bump up the smallest value on the right subtree.
When you're doing this you're always going to take basically the leftmost child node on the right subtree
or the rightmost child node on the left subtree, so for me the leftmost child node on the right Subtree is 33.
You remove 32 and you can replace that with 33 and then remove 33 and you see that 49 is greater than
33 and 64 is greater than 49, so the right truck
trees still holds and 33 is greater than 27 29 is still less than 33
So this whole subtree is still less than 33 and we are done with this problem.