Welcome back.
In this video let's discuss how we can implement this recursively.
This is also going to be pretty straightforward.
So we have our binary tree over here.
And we start at the root node.
So we call the recursive function for the root node.
And what this function will do is it will swap its children so its children are two and three.
So let's swap them.
So we get three and two over here.
All right.
Now we are just going to proceed in the left direction.
So we will go in this direction.
And we will recursively call the same function for this particular node over here.
Now again what will it do.
It will come inside the recursive function and it will swap its children which is null and seven.
So we will get the binary tree in this way.
So we have seven and null.
So these two have been swapped.
All right.
Again we will recursively make the same call.
The we will call the same function over here for this.
That is we moved in the left direction.
So you can see we moved.
We are moving in the left direction right.
So we have this node over here.
And its children are just null and null.
So we are going to swap them but it's not going to have any impact.
And then after that we will again call the function recursively on the null node over here which is
null right.
And at that case we are just going to return.
So that is going to be our base case.
So if the node is going to be null we will just return.
So that is our base case.
So when we call it for this node which is null we will return.
And it'll go in the right direction.
Again, it's going to be null and it's going to return.
So it's done for this part.
All right.
So we went in this direction from node three in the left direction.
And it will return at this point.
Right.
Again we are going to call in the right direction.
So we will make the recursive call on this node.
Again this is null.
So it's going to return because that is our base case.
So this also will return.
So at this point this is done.
So this was the left of node one right.
So again it will return.
So the left of node one is done.
Now we are going to go in the right direction.
And we will make the recursive call on this node over here which will just swap its children.
So these two are going to be swapped.
And we get the binary tree in this way.
So you can see that they were swapped.
Now we will again proceed in the left direction.
From here we will make the recursive call on this node over here.
And it will swap its children which are just null and null.
And then we go in the left direction right.
So this is null and this is null.
So from here we will go in the left direction.
And this is because this is null.
This will just return.
Similarly we go in the right direction because this is null.
It will just return.
So it will return from here.
So the left of this call right when the node was two the left call is done.
So now we proceed in the right direction.
And we will make the call on this node over here.
And again it will swap its children which is which are just null and null.
So it has no impact.
And then from there we proceed in the left direction.
We will make the call on this node which is null which will just return.
Then we proceed in the right right direction which will make the call on this node which is also null.
So it will also return.
So this part is done.
Now this will just return and then it will again return and we are done.
So this is how the recursive function works.
You can see that we passed in this binary tree.
And then we got it inverted.
Or we are getting its mirror image.
Now let's take a quick look at its space and time complexity.
And this is a recursive function.
You can see that the time complexity of this solution is O of n itself.
And we have seen that in the case of the iterative iterative solution also we are getting time complexity
of O of n.
Now you can think of it in this manner.
We are traversing every node one time and then we are just swapping its children.
Right.
So we are doing this operation n times, or they are going to be a total of n recursive calls.
Right.
And I'm not saying that they will be there at the same time, but I'm saying that the total number of
operations that we are doing is going to be n now, whenever we are having the recursive call, we are
just calling, we are swapping its children, and then we will recursively call the same function on
its left and right child.
Now that has already been accounted.
When I say when I say that there they are going to be a total of n n calls on the same recursive function.
So for each call we are just swapping its children.
So that's why we are traversing every node one time.
And hence the time complexity is just going to be O of n.
Now what about the space complexity?
The space complexity is because this is a recursive function is going to be O of the maximum depth because
of the call stack.
Right.
And remember the maximum depth is nothing but the height of the tree.
And this is because of the call stack.
Right.
So we are not using any other space, but because of this space you used on the call stack.
That's why the space complexity is O of max depth.
Now for example, in the in this case over here, what what would be the total number of calls that
can be there.
At the same time, we can have a call over here, over here, over here and over here.
Right.
Because its child is null, you can see that there are total of four calls over here right now.
In the case of a balanced binary tree, the maximum depth is going to be log n.
And that's why we can say that the space complexity is O of log n in the case of a balanced binary tree.