Hello all and welcome back.
So in this video let us continue our discussion on BST class.
And now let's understand insert function.
So let's get started.
Now I'm pretty sure that you must have given it a try before actually explaining you.
I have found another great visualization.
So in through which we will be able to actually understand the insert a lot better.
So let us see that once.
So let me just refresh it once and yeah now it's empty.
Great.
So when we are dealing with an empty overall route right.
So when nothing is there let's say I add ten.
So ten get added like it's 0010.
But I think we can work with that.
So it should be fine.
Now let's say I want to add 15 okay.
Let's see how it will be added.
So I asked for 15.
It checked that okay where 15 should come.
Similarly let's say I want to add five.
Similarly, it will be checked with root and then we say that it is added here.
Now say we enter 20.
And let me just reduce the animation speed a little bit so I can explain you as well.
See note 20 is there.
It is getting checked with this and it says that hey you should be on right now towards the right is
it is interest inserted?
Now let's say we say 12 okay.
And I'm reducing the speed a little bit more.
Now pay attention how the decision is going to get made.
12 it is getting checked.
It says that you should be on right.
It checked and say you should be on left.
Okay.
So what exactly is happening is that we have to reach to the right position somehow and then create
a root there.
That is what we have to do in our insert functionality.
Let us just see one more example.
Say I am inserting in this particular case I am inserting say 14 Okay, so pay attention.
Let me zoom in as well so that we can clearly see what is happening.
I have to insert 14 checked with the values it says go to right now.
Getting checked with the value says go to right, getting checked with the value and say hey, you should
be on this.
So we have added the same.
Great.
So pretty sure this whole helps you to visualize things a lot better.
Again, my whole aim is to make sure that you are able to understand and inside your mind, the whole
picture should be made whenever I ask for any operation.
Okay, great.
So let us now move forward everyone and try to implement the same.
We have the insert here again.
What's going to happen.
We will be saying that BST object dot insert and say we are inserting 20 maybe okay great.
So now let's see what's going to happen Okay I will come on insert.
And what is the base case?
Base case I believe is very easy.
Again self dot root equals to none.
If nothing is there then I am just creating a root.
Sorry, I'm just creating a node and returning that.
I will have to make sure that I return this because my root is getting changed.
So what I effectively mean by that.
In the case when none is there and you are asking me to insert 20, okay, the root which was initially
none root is getting changed, right?
So I can see that how root is changing now.
So I have to make sure that I return this root which you will basically be uh, further, we all will
basically make sure that we are further using the same thing.
Right.
So let us see that once everyone.
If this is the case, then I have to create a new node.
New node.
Okay.
And in this new node what effectively I have to do BST node.
With this data I have to make sure that self dot root is this new node and I can return.
Right everyone.
So that is how I can make sure that I am able to get this particular new node in my root.
Great.
So we have created this particular root, assign that and added our node as well.
Now let us take the case when if data is less than self dot root dot data.
Okay.
In this case what should I do.
I should make sure that in my self dot root.
dot left because the data is less.
Okay, so in this example, if I try to add seven as it is lower, it will go to the left side right.
So if the data is less than root it should go to the left side.
Right everyone.
Now let us see what exactly is going to happen here.
In this I should say that we have to recursively call now to insert.
Right.
So what I can say insert self dot insert data.
And I am again facing the same problem to make sure that I am able to call recursively.
Okay I need to have the node as well in my function or method.
But this is a method which we have made for the outside user.
For example, here I was just saying that hey, I want to insert say seven.
The last one which we added.
now I didn't say that.
Hey, you have to start from root or you have to start from here, right?
I just give the value which I have to add on the same understanding.
This is something which we should avoid.
So what will happen?
Again I will create a separate function insert self and data and this function will in turn call my
insert helper insert helper where Insert helper.
It's going to take self by default.
That is for sure self data and it should take a root as well.
Okay great.
Along with that because it can happen that my root will get updated as we saw in the none case.
Okay, so I should make sure that I update the root whichever is getting returned.
So this function will now not make the change, but rather return on exactly what is happening.
Okay, so root is equal to none.
It should create this new node.
It should create this new node and just return that.
So that when I'm starting to create let's say the first element is 20.
As we discussed root will be none.
I will be returning the new node and that will get updated in my self dot root.
Okay great.
Now let us quickly do for the other then everyone.
I think it's going to be a lot easy now.
So now I can directly just call insert helper with data and root dot left.
Okay, now I should get rid of all these self because we are not working on this self root dot data.
And similarly if this is not the case then else.
And to make it clear, let us keep it node.
Okay not root.
So I will be passing data here.
And self dot root.
So let this be node everyone and node dot data.
And I also have to make sure that if I'm calling on left.
Okay.
Let's say it is something like this.
Where as of now ten is there.
As of now ten is there and I am calling on left.
It is none, but it can again get updated.
So I need to make sure that I have this connection updated from what will be getting returned.
Okay, so this will finally become everyone then node dot left right in a very similar sense node dot
right if it is greater.
So self dot insert.
Helper data node dot.
Right.
And once I'm done with all these things, I can just return the node.
So whatever changes it could have added recursion must have done the work.
I know no need to care of this particular thing that how recursion must have done this work.
I am sure once I made the recursion call, the same is done and we will be able to add.
Okay, so maybe we can check this as well.
So let us quickly check this as well everyone.
Let's say I am adding 20.
Let's say 2510 and say 15 okay.
To print.
What we can do one minute.
So do we have that particular function which we can print it.
So let us copy that.
Okay.
Let us copy the way we were printing with this function.
Again, all these functions we have written already, everyone.
So just using them so that we can see our tree in a better overall printed format, right.
So let me copy this in the BST class.
I should copy this function.
Let us copy on the top so that we can use it internally as well.
And now what I have to do once I have done this print binary t bst object.
Great.
So let us first try to solve this at R and everyone what is going to happen.
I enter 20 initially it is none, so 20 will get created.
Now I'm saying at 25, if you remember the whole animation here, it's going to get checked with the
root and then go to right.
So it's going to be 25.
Similarly for ten and then finally 15.
So this is what I should see.
Let us first run this quickly.
Nope.
No errors are there.
Okay, so there is an error.
BST object has no attribute data.
It's on line number six.
Okay so we are passing a node, right?
I have to pass the root.
My bad.
So root is where everything will be there right.
And yes we are able to see this.
So let us quickly check everyone 20 left ten right 25 seems right, ten left, none right, 15 seems
right and all the others are none.
So yeah, it seems that insert is working fine.
Let us quickly check for search as well if this is working.
So what we have to do?
Print
Search.
Lets search for ten first.
We are getting two so seems like it is working.
We are getting true here.
Okay then let's search for 15 again.
Getting true.
Lets search for 17.
Okay 17.
Also it is giving okay.
It was not updated.
So 17 it is giving false.
Everyone okay.
So the file just takes a second to save.
That's why.
So seems like search is working.
Insert is working now.
Next we have to discuss and implement on delete.
Okay.
What I will also suggest you is that you will have this overall visualizer tool okay.
So in this tool try to just have some cases where you are deleting a node and see exactly what happens
okay.
In the next video we are going to discuss delete in depth.
But for the time being just just see that what's going to happen when we delete nodes in this particular
tool before the next video.
Okay.
So great everyone.
Let us now implement delete in the next video.
Thank you.