Hello all and welcome back.
So in this video let us insert the node at an index.
But using recursion.
Now the same problem we have done by using iteration in the last video.
So please make sure that you see the same.
We have this overall linked list in front of us, right?
And we have the head and we want to insert this node at index three.
Okay.
Now the understanding which we developed in our last video when we were doing the same iteratively is
going to be helpful here as well.
But in recursion, of course, the benefit is that we have to do some part and most of the part recursion
can do for us, right.
So let us now try to follow the framework.
Everyone in recursion I know that I have three steps.
That's how we have understood recursion.
Right.
So the first very first one is your base case okay.
Base case I believe is pretty easy okay.
And let me just write it down so we can extend on it.
Yeah.
Great.
So the first one is just your base case.
Base case I believe is pretty easy.
Okay.
So there can be two cases.
First is when index is zero right.
So we saw that if index is zero we just have to insert at head right.
Second year we have to insert at head.
Whereas if my head is none if my head is none then I have to do something.
Because if head is none then ideally I cannot insert in that right?
If head becomes none.
So for example, let's say it's an empty list and you are asking that hey, insert in the third index
of this list, right?
So that's the problem.
Either the index should be zero or if the index is not zero, okay.
In an empty list, if you are asking that hey, can you insert on the second index?
That's a problem, right?
Because it's an empty list.
Great.
So yeah, that's the overall thing which we have to handle.
Second.
Is the recursive call right.
So the recursive call is going to be something like this.
If we have our head in my head next I can just call the function.
So let's say insert right with the same head but dot next this time.
So again my problem is going to get break like this.
So I'm going to pass a part of my linked list.
That is I'm going to keep it to myself.
And I'm going to pass the head this time.
If I'm doing the same thing then data will remain the same.
That is not a problem and I just have to make sure that index.
Also I reduce by minus one Because if I have index three for this particular head, then the same is
going to be index two for this particular linked list.
Right?
So I hope you are able to understand this for this list.
If the index is three then same is actually index two for this list okay.
So yeah third actually is going to be our work.
Our work.
So in a way we have handled our work when we wrote it for index equals to zero.
Because when the index will be zero that is when we are going to do something.
So due to that in our work we just have to return the head.
Whatever we are getting, we just have to return the head okay.
So let us try and code this all code this everyone okay.
So let us just try to write it here def insert at index recursively.
And here we will be having a head data and index.
Great.
So first of all, let us see if index is zero.
Now you have to understand one thing.
Index zero kind of represents okay that I am at the starting of my list okay.
In a way though, you have to think this after writing the code.
But still let me help you to think this when you will make the recursion calls right when you are going
to make this recursion call.
So first call three is the count.
Sorry, three is the index.
As of now it will become two here, one here, and finally zero here.
Okay.
So I am saying that this particular linked list I want to insert something at its head.
Right.
And what is that something.
It is that new node okay.
So using recursion that is how the flow is actually like happening.
That is the reason that just if you are able to handle this insert at index zero.
That is your work in a way.
Now, if you return this, we have to make sure that we just do this connection again.
Okay.
So I hope now it is a lot clearer why I write like this.
So first is this just maybe we can call return insert at head right.
So we have already seen how this function works.
Pretty easy function.
Next is if head is null then actually we have to print.
That index is out of bounds.
Index is out of bounds.
Because if index is not zero and the head is none, then we kind of have this condition where temp was
none and index was this count was still greater.
Right.
So in a similar way, if head is none, index is out of bounds and we can move forward.
Just return this head only or we can return none as well.
Should be fine.
Last, I just have to call this head dot.
Next is equals to just let recursion do the work.
Okay.
Head dot next data and index minus one.
Once you do this actually the code is going to run pretty well.
Okay so let us just try this once everyone.
Um yeah.
It seems to work.
Let me make it three and let's run this now.
So yeah.
Enter the value.
Let me say ten, 20, 30, 40, 50 minus one.
Okay.
So it is giving an error.
Insert at index.
Okay.
My bad.
It should be at head right.
Great.
So just messed up.
The function should be fine.
Ten 2030 4050 minus one.
And it seems to work.
It is working, right.
So let me just make it a little bit more clear to you all so that you are able to understand how the
flow would have happened.
So what we can do is let me make a copy of this list and help you imagine.
Because if this is clear once, then you will be able to write lots of code of this recursion going
forward.
Okay, great.
So let me just copy this.
Cool everyone.
So pay attention.
What's exactly going to happen.
The same is going to help you write a lots of recursion code on linked link linked list going forward.
Okay cool.
So we have this particular linked list.
I received my call I received this.
So let us write what we received for us here.
The count was three and data was 35 only right.
So this is the count not the count.
Sorry.
Index.
And data.
Right now when I call using recursion.
So just I'm doing it horizontally.
We have as of now seen the working vertically.
Right.
So doing it horizontally when I call the recursion two is going to be the index.
It is going to be 35 still.
Similarly here one is going to be the index.
This is going to be 35.
And here finally when we make this call it is going to be zero and 35 okay.
Now if you see we have actually hit a case when index is zero, right.
So what recursion is going to do based on this thing.
It is a index equal to zero case which we have handled via.
If condition recursion is going to make a new head okay.
It's going to insert that head that is 35.
And after that we will just have these.
I'm just trying it 40 and like this one second.
50.
So pay attention.
What exactly going to happen.
This is what my linked list was.
My whole case actually just boiled down to adding to it.
And now I am returning this new head.
Right?
I am returning this new head because I'm returning this new head here.
Okay.
This overall linked list, uh, code recursion is going to return me the new head.
It is very important that I join this back.
If I don't join this, right.
If I don't join this, then the code is not going to work.
The reason for that is yes, we are going to insert this head.
Okay.
We are going to insert it here.
But when the flow comes back to this code, when the flow comes back to this code, then we have to
make sure that we join this whole flow.
We join this whole flow.
And this is the reason.
This is exactly how the flow is gonna work.
So I hope this is clear.
Now, everyone, let us just one last way.
Look at it in Python tutor as well, because I want to make sure that it is properly clear to you all.
Okay.
So great.
Let me just showcase this to you.
Exactly what's going to get returned the attention.
Yeah.
Let us just remove all this.
Okay.
Cool.
So again okay.
It's in the end.
My bad.
Just me edit the code.
Okay.
So it is expecting inserted header function which we should have here okay.
So it's giving an error that inserted.
It is not here okay.
It was here.
So let me copy this and let me include it here okay.
So it is giving the error that inserted head which we are trying to use that is not present.
Okay, so Python tutor was giving that error.
Now what we have done, we have just copied this right.
Great.
So now once we have copied this, once we have copied this, what we have to do, let us visualize and
seems to work fine now.
Okay everyone.
So just what I have done.
Just the code for insert at index recursively I have added here.
Okay, cool.
So let us first move forward.
Let us first move till the end.
We get the linked list.
So let us go ahead.
Yeah.
See this is where as of now I have my head.
So it is this much only ten, 20, 30.
40, 50.
Now let us move forward.
The functions are going to get defined.
And finally we are going to call insert at index recursively.
Right.
Great.
So first we are going to check if my index is zero or my head is none.
I think both are not true.
So let us move forward.
Okay so I hope you are able to catch this.
Everyone I am checking here if for the index and the head.
These are the two conditions which I have to check because both are not true.
I'm going to move forward.
So let's move forward and see.
Now I'm going to make this call I'm going to make this call.
Okay.
In this call I am just calling buy head dot next.
So this 20th will be the new head data and index minus one.
So index will become two.
Pay attention.
See in the next function which we created recursively head is now pointing to this right.
So my head in a way has changed for this recursive call.
The second recursive call and it is pointing to the second linked list or second node.
It is very analogous to the way we used to do things in linked list and arrays in recursion, right?
Again, this is not the case.
So we have to move forward.
Okay.
Now this is the third in node which is the head for the third function.
Again, no condition is getting satisfied, so we have to remove or move forward.
And now finally we get here.
Now just forget everything.
Okay.
So let me just remove try to remove this as well.
So yeah just now forget everything and try to solve this problem.
Okay.
What if we are just given this particular problem.
I think the case is very easy to understand this problem, right?
We just have a linked list 4050 and the index is zero.
So it is asking me to insert at head right.
So I hope now you are able to understand how recursion is handling this thing.
You forget anything about recursion or anything.
Just think that if you are given this linked list okay, 40 and 50 and if I ask you to insert 35 at
its head, don't you think that it's a direct thing which you can do?
Like you don't need to do any recursion call or anything, right?
So that is why this is one of the base case for our work, which we have to do now.
For this I'm calling inserted head.
We know how that works.
Just simple three lines.
Okay, so inserted head is getting called.
This is the head okay.
It's going to make a new node.
And then that new node is going to get returned.
So this we have seen already by our working.
So yeah let us move forward.
New node getting created.
See here.
So yeah new node getting created.
And this is my new node.
Now this head right.
This head.
First I have to make sure that I make this connection so that I don't lose on anything.
See this is the connection which we make from where is this connection coming.
It is coming from this new node dot next head, something which we have seen already.
Right.
Something which we have seen already.
Let me remove this as well so you don't get confused.
See Newnode.next.
It's making sure that this information, this particular head is not just forgotten or get lost.
Please.
As of now, try to not see this.
Okay?
so zooming in, I think I can make the problem smaller.
We just have to add this 35 node to the head of this sub part of Linkedlist.
Once we do that, once we do that, okay, once we are able to just create this thing, let me just
zoom out.
Yeah.
So yeah great.
We are going to get our head like this.
See insert add index recursively.
It is going to return this thing.
And this is what I want to explain you very nicely.
So pay attention everyone.
This head dot next is going to connect with whatever you return here.
And the return value.
This time it's this node which in turn is making a linked list like this.
Right.
Which is making a linked list like this.
So yeah, I know a little bit, uh, not so cumbersome.
I think using visual, it is a lot clearer now when this head gets returned.
I have to make sure that I again, I update my connections.
If I don't do that, it's going to be a problem.
Else you will not see the answer.
That's why anytime you are calling recursion on a linked list problem, please make sure that you are
reconnecting your all the connections.
Okay, so don't just leave and call it collect that head and make sure that you are connecting it again.
If you don't, then this connection will remain intact and you will not be adding anything.
Okay, so great everyone, now let us move forward.
I am pretty sure with this overall visualization is not clear.
So see now just the second I did this, this was the return value head dot.
Next we just updated this right.
We have just updated this and now everything is going to remain the same.
This now gets returned.
It's going to get connected here which is the same thing okay.
This is going to get returned this list.
It's going to get connected which is the same thing.
And finally the last one inserted node index recursively and we have our head like this.
Okay, so I'm pretty sure everyone now with this visualization, it is a lot clearer on both the things
that exactly what was happening.
I want to make sure that you actually understand this line.
The line on 61, okay.
If you don't connect, then this connection will not break and you will not be able to make this new
connection.
That's why in recursion it is very, very much important that you reconnect your node.
Okay.
So yeah I that was the overall explanation.
Everyone please make sure that you just try to dryrun it once again and see that you are able to understand
each and every step.
Moving forward.
We are going to do more problems using iteration and recursion so that it becomes a lot clearer the
time which you are spending right now to make your understanding strong, is going to make sure that
you are able to do each and every question in linked list.
All the question will be a lot easier if you just understand these things once.
Okay, cool.
Then everyone let's meet in the next video.
Thank you.