Welcome back.
Now in this video let's try to think how we can solve this question.
Now we will try to solve this question iteratively and recursively.
First let's talk about how we can solve this question iteratively.
Let's say this is the tree which is given to us.
Now if we want to invert this iteratively, we are going to traverse the given binary tree using the
breadth first search approach.
So we are going to have a Q.
All right.
So we are just going to go through the given tree breadth first.
And at every node we will just swap the left with the right.
So that's it.
So it's pretty straightforward.
So for breadth first search we'll have a Q.
And starting at the root we will insert the root into our q.
So we have the Q and we have one over here in the Q.
And then we have the while loop.
And this will keep looping as long as something is there in the q.
So this is what we have seen many times when we implemented breadth first search.
So let's go ahead.
Now inside this we will first dequeue.
So we take this one out and then we are just going to swap.
So over here we are going to swap its left and its right for this particular node.
So over here the left is two and the right is three.
So we are going to swap these two.
So let's go ahead and swap these two.
So we get three over here and two over here.
And its children are how they are at the moment itself.
So for three the left is null and the right is seven.
And for two the left is four and the right is five.
So this is what we have done at this point.
We have just swapped these two right, the left and right of the current node which is one.
Now the current node is one.
We have just dequeued that right.
And for the next step we are just going to check its left and right.
And if there is a left child we will enqueue it.
And if there is a right child we will enqueue it.
So this is what we have done many times when we have discussed breadth first search.
So we are just implementing the same thing over here because we are doing this using BFS itself.
All right.
So let's go ahead and enqueue the left which is three and the right which is two two.
All right.
Now again we proceed.
We see that the queue is not empty.
So we come and we dequeue from the queue.
All right.
So we dequeue from the queue.
And then we are going to swap the left and right of this particular node which is three.
So let's go ahead and do that.
So we swap these two.
So we have null and seven which is changed to seven and null over here.
And then we come and check its left and right and enqueue the children.
So its children are seven only right.
So null is not enqueued.
So we are just checking if there is a valid child which is not null, and if it is there we will enqueue
it.
And again we come over here we see that the queue is not empty.
We'd Q two all right.
So we'd q two.
And then we are going to swap its children which is four and five.
So let's go ahead and swap them.
And over here we get five and four.
And then we are just going to enqueue its children which is five and four.
So we are going to get five and four over here its left and right child.
And then that's it.
So this this iteration is over.
This looping is over again.
We check if the queue is empty.
We see that the queue is not empty.
We will we will dequeue seven.
But then it does not have any children.
Right.
To n q and then it does not have any meaningful children.
It just has null and null.
So we will swap null null.
But but it does not have any effect.
So again we come over here.
At that point we will take out five.
We will dequeue five.
And its children are also null and null.
So we swap them and we don't have anything to enqueue.
Again we come over here and we will dequeue four and we will swap its children, which is just null
and null.
And we don't have anything to enqueue.
And at this point the queue is empty and we are done.
And you can see that we have got the binary tree tree and it has been inverted.
Or every corresponding left node has been swapped with with its corresponding right node.
Or we have got the mirror image of the given binary tree.
All right.
So this is the iterative approach where we have used BFS.
Now let's take a quick look at the complexity analysis of this solution.
Over here we can see that the time complexity is just O of N right.
It's going to be linear time because we are just implementing BFS.
And we know that the time complexity of BFS is O of n.
So what is that we are doing over here?
We are visiting every node one time, and then we are doing some constant time operations during every
visit.
Right.
So what are these operations we are going to dequeue.
We are going to swap and then we are going to add to the queue.
So that is happening over here.
These are just constant time operations.
And this is going to happen n times.
Right.
Because we are visiting every node once.
And for this we will use the while loop over here.
So this is BFS.
And so the time complexity is just going to be O of a constant into n.
And we can remove the constant.
And that's why the time complexity of this solution is O of n.
Now what about the space complexity.
Now what are the things over here that takes space that can scale when the input scales?
It is this queue over here.
Right.
So the space complexity is also going to be o of n by two, because we have seen that in the case of
a full binary tree there can be n by two leaf nodes.
Right.
And all these n by two leaf nodes will be there at the same time in our queue.
So we have seen that previously.
That's why we can say that the space complexity is also O of n.