1
00:00:00,620 --> 00:00:01,640
Welcome back.

2
00:00:01,640 --> 00:00:05,630
Now in this video let's try to think how we can solve this question.

3
00:00:05,630 --> 00:00:09,860
Now we will try to solve this question iteratively and recursively.

4
00:00:09,860 --> 00:00:13,550
First let's talk about how we can solve this question iteratively.

5
00:00:13,550 --> 00:00:16,850
Let's say this is the tree which is given to us.

6
00:00:16,850 --> 00:00:23,120
Now if we want to invert this iteratively, we are going to traverse the given binary tree using the

7
00:00:23,120 --> 00:00:24,470
breadth first search approach.

8
00:00:24,470 --> 00:00:26,090
So we are going to have a Q.

9
00:00:26,090 --> 00:00:26,480
All right.

10
00:00:26,480 --> 00:00:30,080
So we are just going to go through the given tree breadth first.

11
00:00:30,080 --> 00:00:33,980
And at every node we will just swap the left with the right.

12
00:00:33,980 --> 00:00:34,520
So that's it.

13
00:00:34,520 --> 00:00:35,960
So it's pretty straightforward.

14
00:00:35,960 --> 00:00:38,480
So for breadth first search we'll have a Q.

15
00:00:38,480 --> 00:00:42,470
And starting at the root we will insert the root into our q.

16
00:00:42,470 --> 00:00:45,440
So we have the Q and we have one over here in the Q.

17
00:00:45,440 --> 00:00:47,000
And then we have the while loop.

18
00:00:47,000 --> 00:00:50,360
And this will keep looping as long as something is there in the q.

19
00:00:50,360 --> 00:00:53,720
So this is what we have seen many times when we implemented breadth first search.

20
00:00:53,720 --> 00:00:54,800
So let's go ahead.

21
00:00:54,800 --> 00:00:57,290
Now inside this we will first dequeue.

22
00:00:58,200 --> 00:01:02,370
So we take this one out and then we are just going to swap.

23
00:01:02,370 --> 00:01:06,570
So over here we are going to swap its left and its right for this particular node.

24
00:01:06,570 --> 00:01:09,480
So over here the left is two and the right is three.

25
00:01:09,480 --> 00:01:11,100
So we are going to swap these two.

26
00:01:11,130 --> 00:01:13,110
So let's go ahead and swap these two.

27
00:01:13,140 --> 00:01:16,110
So we get three over here and two over here.

28
00:01:16,110 --> 00:01:19,500
And its children are how they are at the moment itself.

29
00:01:19,500 --> 00:01:22,950
So for three the left is null and the right is seven.

30
00:01:22,950 --> 00:01:25,620
And for two the left is four and the right is five.

31
00:01:25,620 --> 00:01:27,330
So this is what we have done at this point.

32
00:01:27,330 --> 00:01:31,860
We have just swapped these two right, the left and right of the current node which is one.

33
00:01:31,860 --> 00:01:33,810
Now the current node is one.

34
00:01:33,810 --> 00:01:35,310
We have just dequeued that right.

35
00:01:35,310 --> 00:01:39,480
And for the next step we are just going to check its left and right.

36
00:01:39,480 --> 00:01:42,030
And if there is a left child we will enqueue it.

37
00:01:42,030 --> 00:01:44,250
And if there is a right child we will enqueue it.

38
00:01:44,250 --> 00:01:47,580
So this is what we have done many times when we have discussed breadth first search.

39
00:01:47,580 --> 00:01:52,770
So we are just implementing the same thing over here because we are doing this using BFS itself.

40
00:01:52,770 --> 00:01:53,220
All right.

41
00:01:53,220 --> 00:01:58,200
So let's go ahead and enqueue the left which is three and the right which is two two.

42
00:01:58,230 --> 00:01:58,710
All right.

43
00:01:58,740 --> 00:02:00,120
Now again we proceed.

44
00:02:00,120 --> 00:02:02,010
We see that the queue is not empty.

45
00:02:02,010 --> 00:02:04,770
So we come and we dequeue from the queue.

46
00:02:05,460 --> 00:02:05,850
All right.

47
00:02:05,850 --> 00:02:07,680
So we dequeue from the queue.

48
00:02:07,680 --> 00:02:12,510
And then we are going to swap the left and right of this particular node which is three.

49
00:02:12,510 --> 00:02:14,070
So let's go ahead and do that.

50
00:02:14,070 --> 00:02:16,110
So we swap these two.

51
00:02:16,440 --> 00:02:20,730
So we have null and seven which is changed to seven and null over here.

52
00:02:20,730 --> 00:02:25,350
And then we come and check its left and right and enqueue the children.

53
00:02:25,350 --> 00:02:27,600
So its children are seven only right.

54
00:02:27,600 --> 00:02:29,430
So null is not enqueued.

55
00:02:29,430 --> 00:02:34,320
So we are just checking if there is a valid child which is not null, and if it is there we will enqueue

56
00:02:34,320 --> 00:02:34,590
it.

57
00:02:34,590 --> 00:02:37,530
And again we come over here we see that the queue is not empty.

58
00:02:37,560 --> 00:02:39,030
We'd Q two all right.

59
00:02:39,030 --> 00:02:40,470
So we'd q two.

60
00:02:40,470 --> 00:02:44,010
And then we are going to swap its children which is four and five.

61
00:02:44,010 --> 00:02:45,420
So let's go ahead and swap them.

62
00:02:45,420 --> 00:02:47,550
And over here we get five and four.

63
00:02:47,550 --> 00:02:51,600
And then we are just going to enqueue its children which is five and four.

64
00:02:51,600 --> 00:02:55,260
So we are going to get five and four over here its left and right child.

65
00:02:55,260 --> 00:02:56,430
And then that's it.

66
00:02:56,430 --> 00:02:58,020
So this this iteration is over.

67
00:02:58,020 --> 00:02:59,400
This looping is over again.

68
00:02:59,400 --> 00:03:00,960
We check if the queue is empty.

69
00:03:00,990 --> 00:03:03,180
We see that the queue is not empty.

70
00:03:03,210 --> 00:03:04,950
We will we will dequeue seven.

71
00:03:04,950 --> 00:03:07,410
But then it does not have any children.

72
00:03:07,410 --> 00:03:07,620
Right.

73
00:03:07,620 --> 00:03:10,350
To n q and then it does not have any meaningful children.

74
00:03:10,350 --> 00:03:11,880
It just has null and null.

75
00:03:11,880 --> 00:03:13,290
So we will swap null null.

76
00:03:13,290 --> 00:03:15,030
But but it does not have any effect.

77
00:03:15,030 --> 00:03:16,410
So again we come over here.

78
00:03:16,410 --> 00:03:18,030
At that point we will take out five.

79
00:03:18,030 --> 00:03:19,290
We will dequeue five.

80
00:03:19,290 --> 00:03:21,480
And its children are also null and null.

81
00:03:21,480 --> 00:03:24,570
So we swap them and we don't have anything to enqueue.

82
00:03:24,570 --> 00:03:29,310
Again we come over here and we will dequeue four and we will swap its children, which is just null

83
00:03:29,310 --> 00:03:29,790
and null.

84
00:03:29,790 --> 00:03:31,890
And we don't have anything to enqueue.

85
00:03:31,890 --> 00:03:34,770
And at this point the queue is empty and we are done.

86
00:03:34,770 --> 00:03:39,540
And you can see that we have got the binary tree tree and it has been inverted.

87
00:03:39,540 --> 00:03:44,700
Or every corresponding left node has been swapped with with its corresponding right node.

88
00:03:44,700 --> 00:03:48,030
Or we have got the mirror image of the given binary tree.

89
00:03:48,030 --> 00:03:48,450
All right.

90
00:03:48,450 --> 00:03:51,450
So this is the iterative approach where we have used BFS.

91
00:03:51,450 --> 00:03:56,250
Now let's take a quick look at the complexity analysis of this solution.

92
00:03:56,760 --> 00:04:01,350
Over here we can see that the time complexity is just O of N right.

93
00:04:01,350 --> 00:04:04,650
It's going to be linear time because we are just implementing BFS.

94
00:04:04,650 --> 00:04:07,890
And we know that the time complexity of BFS is O of n.

95
00:04:07,890 --> 00:04:09,720
So what is that we are doing over here?

96
00:04:09,720 --> 00:04:15,510
We are visiting every node one time, and then we are doing some constant time operations during every

97
00:04:15,510 --> 00:04:15,810
visit.

98
00:04:15,810 --> 00:04:16,110
Right.

99
00:04:16,110 --> 00:04:18,780
So what are these operations we are going to dequeue.

100
00:04:18,810 --> 00:04:21,480
We are going to swap and then we are going to add to the queue.

101
00:04:21,480 --> 00:04:22,620
So that is happening over here.

102
00:04:22,620 --> 00:04:24,660
These are just constant time operations.

103
00:04:24,660 --> 00:04:26,670
And this is going to happen n times.

104
00:04:26,670 --> 00:04:26,880
Right.

105
00:04:26,880 --> 00:04:28,830
Because we are visiting every node once.

106
00:04:28,830 --> 00:04:31,950
And for this we will use the while loop over here.

107
00:04:31,950 --> 00:04:33,450
So this is BFS.

108
00:04:33,450 --> 00:04:38,220
And so the time complexity is just going to be O of a constant into n.

109
00:04:38,220 --> 00:04:39,720
And we can remove the constant.

110
00:04:39,720 --> 00:04:42,780
And that's why the time complexity of this solution is O of n.

111
00:04:42,780 --> 00:04:44,790
Now what about the space complexity.

112
00:04:44,820 --> 00:04:49,260
Now what are the things over here that takes space that can scale when the input scales?

113
00:04:49,260 --> 00:04:50,520
It is this queue over here.

114
00:04:50,520 --> 00:04:50,760
Right.

115
00:04:50,760 --> 00:04:56,880
So the space complexity is also going to be o of n by two, because we have seen that in the case of

116
00:04:56,880 --> 00:05:00,330
a full binary tree there can be n by two leaf nodes.

117
00:05:00,330 --> 00:05:00,660
Right.

118
00:05:00,660 --> 00:05:04,980
And all these n by two leaf nodes will be there at the same time in our queue.

119
00:05:04,980 --> 00:05:06,600
So we have seen that previously.

120
00:05:06,600 --> 00:05:11,010
That's why we can say that the space complexity is also O of n.