Welcome back.
Let's now go ahead and write the function to invert the given binary tree recursively.
So over here is the previous function that we have written.
So let's write the new function here itself.
So let's call this function invert recursive.
And this function is also going to take in the root.
So we have root over here.
Now once we are inside this function we will think of the base case because this is going to be a recursive
solution.
So the base case is going to be when the root is equal to null we will just return.
So if root is equal to null.
In that case, we will just return.
Now remember this is not necessarily to be called root.
Let me just call this node.
So this is actually the node with which we are calling the function.
So when that is actually equal to null we will just return.
All right.
Now if this is not the case then for that particular node we will swap.
So at this point we are going to swap the left and the right of that particular node using a temp variable.
So let's say const temp.
Is equal to root or at this point node right, node dot left.
Let's call it left.
Let me just take this down a bit so that we can see this.
And then we will say node dot left.
Is equal to no dot, right?
And node dot right is equal to temp.
So in this way we are swapping the left and right.
Now we are going to recursively call the same function the invert recursive function on the left node
and the right node.
So this is how this function works.
So let's call this recursively.
So we have invert recursive.
And we are going to pass the left node.
So node dot left.
And we are doing the same thing for the right node.
So invert recursive and we will pass node dot right.
And that's it.
And once we are back, we just need to return the node.
So that's mentioned in the question right.
So we take in the root and we're going to return the root.
So over here it's going to be the node.
So initially we will call this function with the root.
So when we return it we will be returning that particular root itself.
So that's it.
So let's go ahead and test our code.
So let me just comment this and we're going to call the invert recursive function.
And we will pass three dot root over here.
All right.
Now again, let me just draw this binary tree.
So we are having this binary tree and then we will be inverting this one over here using our recursive
function.
So this is the binary tree which we have created over here.
All right.
Now let's go ahead and call the function and check whether our code is working.
So let's run it.
All right.
So we have done it.
Now let's check what we are getting.
So we have again the root is the same which is one.
Now let's open it up.
So let's take a look at the left and right child of this.
Once it is inverted right.
So we have the left is three and the right is two.
So yes it's working.
So let's just draw this out parallely.
So we have one and the left is three and the right is two.
So yes this worked.
Now let's continue.
Let's open this up.
And then we have the left.
Over here is five.
And the right is null.
And you can see, yes, this part has been reversed.
Right?
This part also has been reversed.
Now let's continue.
Let's open this up.
We see that over here the left is null.
So the left is null and the right has value seven.
So yes we can see this part.
This is this was null right.
So this is also now reversed.
All right.
Now let's go ahead and open this up.
And we will get null and null.
So we have null and null.
So yes this is also correct.
Now let's check the children of two.
So we go this way we can see that the left is null.
And the right is for.
So yes, this part has been inverted.
And let's open this part over here.
We can see the left is null and the right has value six.
So this is null and this has six which is this part has been inverted.
Now if we just open this up we'll see.
It has null and null as the children.
So yes our function is working.
Now let's just trace the code and see what's happening over here.
So for this let me just um, take an example.
Let's just, uh, make this a bit smaller so that we can see it.
All right, so, yes, we are over here.
Now let's try to trace the function.
So this is the binary tree.
So initially one is passed right.
So initially one is passed.
Now we are checking if this is null.
No it's not null.
So we come over here and then this part swaps these two.
Right.
So we we get these two.
These two will be swapped.
And then the children of it is not yet swapped at this point.
Now we are going to recursively call it at the left which is for this one.
Right.
So when we call it over here its children that is these two will be swapped and we will get it five
and N over here.
But these are not yet swapped.
Now again that's in in a recursive call.
Right.
So after this is swapped again when we come over here it will recursively call it for its children.
And we will see that this over here is null.
So it will come over here and it will return.
So this is returning.
Then it will come over here and it will swap its children, which is just null and null.
So it does not have any impact.
And once this is done we will return.
So this function call will be over right.
For swapping the call where we swap these two.
So that was part of um.
Now let's just trace what is happening in the code.
So this is the binary tree and we are passing the root of it.
Right.
So initially we are calling it with the root.
So the node is initially the root which is one.
We are checking if this is null.
No it's not.
So we come over here and we will swap its left and right.
So this is created right.
So this part is done but its children are not yet swapped.
And let me also write the call stack over here.
We just called the recursive function with the root node which was one.
So it's there in the call stack.
It's not yet returned.
So we come over here at this point.
Now we are going to call the same function with the left which is with three.
So let me write this over here.
So we have R and we are calling it with node three.
So again we come inside the function.
We see that this node over here is not null.
This is not null.
So we swap its left and right.
So this these two get swapped and we get five and n over here.
Right.
And then we again come over here.
And we are going to call it with the left node which is five at this point.
So let me write that over here we recursively call the same function with five with node five.
So we come inside this we are checking if the node is null.
No its not null.
So we come over here and we swap its children.
Right.
So these two these seven and n get swapped and we get n and 7NN means null.
We get null and seven over here right.
So again we come over here and we are going to call the same invert recursive function with the left
node which is null.
So we are going to call it with null at this point.
And we come inside the function again.
And over here we see that that particular node is null.
So this returns right.
So this returns.
So we come back over here.
So this is done.
And this is done for the call where we had the node as five.
So we come to this part which is the recursive call on the right node which is seven over here.
So a call is made.
Let me write it as R with seven.
So the recursive call is made with node seven.
Again its children are swapped.
We come inside.
We see that this is not null.
So we come over here.
Its children are swapped which is null and null.
So these are swapped.
It does not have any impact.
Then we call it on its left child which is again null.
So we come over here and we write it.
So we have a call with null.
We come inside the function, it returns.
Then we come over here.
Right.
So this is part of the call with node seven its children were swapped and we called it on its left child.
Now we are going to call it on its right child which again is null.
So that is going to be another null call which will return.
All right.
So this is done.
So at this point for the call with node seven the left and right is done.
And this this call will be over.
Right.
So this call is over and it will return.
It will return.
Now this was part of the call where we had node five.
Its left was done and its right.
So this is also done right.
So this will return.
And this call is done now.
Now we are coming over here for three.
So we did the call for the left.
That's how we came to five.
But now we are going to the right which is this part over here.
Right.
So we are going to the right and again its null.
So it will come to the call stack but it will immediately return at this point.
All right.
So this will now return.
This will now return right.
So this is done.
Now we come over here.
This was part of the left call of node one.
Now we go in this direction right.
So we are going to call the right node.
So this is the particular node at this point which is this line.
Right.
So we again come inside the function.
This is not null.
So what do we do.
We swap.
So these two get swapped right.
So these two these two get swapped for and n and we get n and four over here.
And then we call it on its left.
It will return because this is null.
Then we call it on its right which is this line over here.
So this is the current node at this point.
So its children will be swapped.
So these two will be swapped.
And we get N and six.
Over here we make the call on its left which will return because this is null.
Then we make the call on its right again its null and null.
So it does not have any impact and then it will return.
We come back over here.
And then this also returns and this also returns.
And we are done right.
So we are done.
So this is how the recursive function works.
Now what about the space and time complexity of this solution.
Let's take a quick look.
Now the time complexity is again going to be o of n right.
The time complexity is nothing but O of n.
Why is that so?
Because we are just traversing through the binary tree right.
So for every node, for every node we will make one recursive call.
So for every node we will make one recursive call.
So there will be a total of n calls.
So for each of these calls we are doing some constant time operations which is swapping.
And then again calling.
Calling the functions again is already accounted for in our N calls.
So for each of these we are just doing some constant operations time operations inside the calls.
So the time complexity is going to be O of N.
What about the space complexity.
It will depend on the on the maximum depth right.
So in this case we will do one call over here.
And then it comes over here.
We do a call over here.
And then we do a call over here for its child.
Right.
So there's a total of one two, three, four five calls at a time.
So we can say that the space complexity is going to be the of the order of the maximum depth.
Now, if the tree is balanced, this is going to be of the order of log of n.
All right.
So because for a balanced binary tree the maximum depth is going to be of the order of log of n.
Right.
So the space complexity over here is going to be maximum depth.
And if it is a balanced binary tree it's going to be O of log of n.