Okay, let's have a look at how to insert some elements into a binary search tree. So let's dive right in. So first, to add elements to our binary search tree, we need to make sure that the elements we're adding are actually comparable, meaning that we can order them in some way inside the tree. Meaning at every step, we know whether we need to place the element in the left subtree or the right subtree. And we're going to encounter essentially four cases. So when inserting an element, we want to compare the value to the value of the current note we're considering to do one of the following things.

Either we're going to recurse down the left subtree because our element is smaller than the current element, or we're going to recurse down the right subtree because our element is greater The current element, or it might be a cat case that the current element has same value as the one we're considering. And so we need to handle duplicate values if we're deciding to add duplicate values to a tree or just ignoring that. And lastly, we have the case that we've hit a null node, in which case it's time to create a new node and insert it in our tree. Let's look at some animation now. So on the left, I have a bunch of insert instructions. So we have all these values we want to insert into our binary search tree.

And currently the search tree or the binary search tree is empty. The first one, insert seven, so seven becomes the root of the tree because it's the first node. Next we want to insert 20. So 20 is greater than seven. So inserted To the right. Next we want insert five.

So we always start at the root when are inserting, and that's an important point. So you start at the root, and then you move your way down the tree to figure out where you want insert the node. So we start at the root, and then we're like, oh, five is less than seven, so we're going to insert it to the left. Now 15, start at the root, go to the right, because 15 is greater than seven. then to the left here, 16 is less than 20. At 10.

Now four, so four is less than seven, move left, four is less than five, move left, create the new node. Now we have four again. So let's see what happens here. So seven moves to the left, move to the left. Now we've encountered a value that already exists in our tree. So as I said before, if your tree supports duplicate dies, now's the time to add another node.

And you would either pick by convention if you want it on the left or on the right. Otherwise you do nothing, I'm going to choose to do nothing. I will insert 33. So start the route, go the right because 33 screener, go to the right again. Now insert two, so two smaller than everything in our tree, so it would go all the way to the left. Now try and see where 25 would go.

So 25, so you can go to the right, then we're going to go to the right again, because it's greater than 20. But we're going to go left now because it's less than 33. And finally, six. So once left once, right, and we've in inserted everything into our binary search tree. So on average, the insertion time is going to be logarithmic. But in the worst case, this behavior could degrade to linear time.

Let's have a look at that. So if our instructions are the following insert 12345 and six, so we start at one. Then we're going insert two. So as soon as we go to the right, okay, now let's insert three, well, three is greater than everything. So I have to place the right again, how about four, okay, four is also greater than everything. Oh, looks like we're creating this line now.

And now six, six is still greater than everything. So as you can see, this type of linear behavior is really bad. And we don't want to create a lines like this because if we want to query where six is in the tree, if we want to remove five or do anything on our binary search, we first need to Find the node. That's going to take linear time. And this is bad. It's one of the reasons why people haven't invented things like balanced binary search trees, or self balancing trees which bounce themselves as you insert nodes.

We'll be getting to that later. But that's it for insertion. It's really simple. Don't overcomplicate it. So next video, we're gonna look at removals for binary search trees. But also, if you want some source code for binary search tree, I've implemented one, just go to my GitHub repository and look under the binary search tree folder.

I'm going to be reviewing the code at the end of this series. So stay tuned for that, guys. Thanks so much for watching. Any questions? Just drop a comment. I'd love reading them.

Alright, see ya.