Welcome back.
Let's now go ahead and write the function to invert the binary tree given to us iteratively.
So let's call this function invert iterative.
All right.
Now this function is going to take in the root of the binary tree.
And this function will return the root after it inverts the tree.
So this is what is mentioned in the question.
So finally, after doing some operations, we will just return the root back.
All right.
Now over here we are proceeding with the iterative solution.
So this will involve using a queue.
And it's similar to breadth first search.
So we will be going through the given tree breadth first and then inverting the respective nodes.
Right.
So let's go ahead.
Now before we start we will just check whether the root is null.
So if the root is null the binary tree is empty.
And we will just return in that case.
So if root is equal to null.
In that case, we will just return.
All right.
Now, if this is not the case, let's have a queue.
So let's say const queue and we will fill the route into our queue.
And then we will have a while loop like we have seen in the case of a vanilla breadth first search.
Right.
So this is just breadth first search over here.
So as long as something is there in the queue.
So while queue dot length we will keep looping.
Now, once we are inside this while loop, we will dequeue from the queue.
So let's say const and let's call it current.
That's equal to q dot shift.
So we take the first element.
And again, remember in the interview you have to explain that you're using an array to implement a
queue over here to save time.
Ideally this should be implemented using a linked list only.
Then when we'd queue, we will get a constant time operation right over here.
Because we have used an array, this would be an O of N operation.
But then because this is not the central part in this question, because the central part is this.
Right.
Inverting the given binary tree.
So if you just mention this to your interviewer, he or she will will be okay with that.
So let's proceed.
So we dequeue from the queue.
Now let's swap the elements.
All right.
So we are at a particular node or a vertex.
Now we are just going to swap the left and right of that particular node.
So let's go ahead and do that.
So we can say let temp.
Let's use a temp with temporary variable.
So let temp is equal to current dot right.
And then we will say current dot right is equal to current dot left.
All right.
And then we will say current dot left.
Is equal to temp.
So we have swapped the left and right for that particular node.
And then we will just check if there is a left node we will enqueue it.
And if there is a right load right node we will enqueue it.
So if current dot left in that case we will just say queue dot push.
Current left.
And if there is a right node.
So if current dot nine.
Right.
Then we'll say Q dot push right.
Current dot right.
All right.
So that's it.
So this should do the work.
All right.
So what are we doing over here.
We are going through the binary tree breadth first.
So we're doing a breadth first traversal.
And then at each node we are just swapping the left and the right.
So this is what is happening over here.
Now let's go ahead and call this function and test it.
So over here again to test this we have our node and binary tree class.
And we have the insert function over here.
Using this we are creating a binary tree.
And then we are inserting these values into the binary tree.
Now let's just call this function.
And let's see whether we are able to invert the given binary tree.
So over here we have in invert iterative.
And then we are going to pass the root.
So that's tree dot root.
All right, now, before we execute this, let me just draw this out so that we can check whether the
tree has been successfully inverted.
Right.
So let's go ahead and draw this over here.
So we have one which will be the root.
Then we have two and three.
So we have two and then we have three.
And then we have four and null.
So this is four and this will be null.
And then we have null and five, so we have null.
And five.
And then we have six and null.
So we have six over here.
Null over here.
And finally we have seven over here.
So that would be this over here right.
This is seven.
So this is how the binary tree looks after we call the insert function.
Now we are just going to call the insert function which is implemented iteratively.
And we will pass the root which is this node over here.
So let's go ahead and run our code.
All right, now let's see what we are getting.
And we are getting back the root.
The root at this point is again one which is correct.
And let me just open this up.
So we have three and two.
So yes these two have been swapped.
Right.
So let's parallelly write it over here so that we can visualize it.
So we have one.
So let me just write it over here.
And then we have three and two.
So yes, these two have been inverted right now.
Let's proceed and open up the remaining part.
So over here you can see the children of.
This node, which is three.
Write the children of three over here are.
Five in the left part and right is null.
So five is left.
And let me just draw that over here five is left and the right is null.
So that is correct right.
So these two also have been inverted.
And we have seen that these two have been inverted.
So let's proceed.
Now again let's open this up.
So for five the children are left is null and right has value seven.
So let me just draw that over here.
So left is null and right has the value seven.
So yes these two also have been inverted right.
So this is null and this is also null.
So these two also have been inverted.
So that's also correct.
So let's proceed.
Now if you if you see for seven you will just get that both of them have null.
So the children of seven will just be null.
So that's also correct.
Now let's proceed.
Now let's try for the children of two.
Right.
So let's go to that level.
Let's go back.
So.
Yes, this is true.
Right.
So for two the children the left is null and the right has value four.
So let's draw that.
So the left is null.
And the right has value for.
And you can see that these two have been inverted.
So yes, this is also correct.
Now let's look at the children of for.
So you can see the left is null and the right has the value six.
So let's draw that.
So the left is null.
The right has the value six.
So yes these two also have been inverted.
And if you just check the children of six you will just have null and null which is correct.
So yes our function has worked.
So this has been successfully inverted.
Now let's go ahead and take a quick look at the space and time complexity of our solution.
So for this let me just make clear this up.
So we'll just clear this up.
All right.
So when it comes to the space and time complexity, first let's take a look at the time complexity.
So here is our function.
Now we can see that this is just breadth first search.
Right.
So we know that the time complexity of breadth first search is O of n because we are visiting every
node once and then we are doing some constant time operations.
Right, which is dequeuing and then swapping and then n queuing.
Right.
So these are just constant time operations.
So this is happening for n times because every vertex, every node will be there in the queue at one
point or the other.
Right.
So we will get everything into the queue because we are traversing through every node.
So that's why the time complexity of this solution is O of n.
And what about the space complexity?
The space complexity also is going to be o of N right.
Why is that?
So the queue in the worst case can have n by two elements.
For the case of a full binary tree where the leaves will have n by two elements, right.
So we have seen that in previous videos where we have discussed this many times.
So I'm not repeating it over here.
And one by two is a constant.
So we can just remove this and we get that.
The space complexity also of this solution is equal to o of n.