1
00:00:00,680 --> 00:00:01,760
Welcome back.

2
00:00:01,760 --> 00:00:08,480
Let's now go ahead and write the function to invert the binary tree given to us iteratively.

3
00:00:08,480 --> 00:00:12,140
So let's call this function invert iterative.

4
00:00:14,660 --> 00:00:15,170
All right.

5
00:00:15,170 --> 00:00:19,490
Now this function is going to take in the root of the binary tree.

6
00:00:22,460 --> 00:00:26,930
And this function will return the root after it inverts the tree.

7
00:00:26,930 --> 00:00:29,030
So this is what is mentioned in the question.

8
00:00:29,030 --> 00:00:33,080
So finally, after doing some operations, we will just return the root back.

9
00:00:33,920 --> 00:00:34,430
All right.

10
00:00:34,460 --> 00:00:37,760
Now over here we are proceeding with the iterative solution.

11
00:00:37,760 --> 00:00:39,890
So this will involve using a queue.

12
00:00:39,890 --> 00:00:41,750
And it's similar to breadth first search.

13
00:00:41,750 --> 00:00:47,900
So we will be going through the given tree breadth first and then inverting the respective nodes.

14
00:00:47,900 --> 00:00:48,230
Right.

15
00:00:48,230 --> 00:00:49,100
So let's go ahead.

16
00:00:49,100 --> 00:00:52,220
Now before we start we will just check whether the root is null.

17
00:00:52,220 --> 00:00:55,430
So if the root is null the binary tree is empty.

18
00:00:55,430 --> 00:00:57,470
And we will just return in that case.

19
00:00:57,470 --> 00:01:00,380
So if root is equal to null.

20
00:01:01,260 --> 00:01:03,120
In that case, we will just return.

21
00:01:04,700 --> 00:01:05,090
All right.

22
00:01:05,090 --> 00:01:07,520
Now, if this is not the case, let's have a queue.

23
00:01:07,520 --> 00:01:12,980
So let's say const queue and we will fill the route into our queue.

24
00:01:13,970 --> 00:01:18,950
And then we will have a while loop like we have seen in the case of a vanilla breadth first search.

25
00:01:18,950 --> 00:01:19,100
Right.

26
00:01:19,100 --> 00:01:20,930
So this is just breadth first search over here.

27
00:01:20,930 --> 00:01:23,570
So as long as something is there in the queue.

28
00:01:23,570 --> 00:01:26,150
So while queue dot length we will keep looping.

29
00:01:28,200 --> 00:01:32,250
Now, once we are inside this while loop, we will dequeue from the queue.

30
00:01:32,250 --> 00:01:35,310
So let's say const and let's call it current.

31
00:01:35,930 --> 00:01:38,690
That's equal to q dot shift.

32
00:01:40,370 --> 00:01:41,810
So we take the first element.

33
00:01:41,810 --> 00:01:46,820
And again, remember in the interview you have to explain that you're using an array to implement a

34
00:01:46,820 --> 00:01:48,290
queue over here to save time.

35
00:01:48,290 --> 00:01:51,170
Ideally this should be implemented using a linked list only.

36
00:01:51,170 --> 00:01:55,070
Then when we'd queue, we will get a constant time operation right over here.

37
00:01:55,070 --> 00:01:58,340
Because we have used an array, this would be an O of N operation.

38
00:01:58,340 --> 00:02:02,870
But then because this is not the central part in this question, because the central part is this.

39
00:02:02,870 --> 00:02:03,080
Right.

40
00:02:03,080 --> 00:02:04,610
Inverting the given binary tree.

41
00:02:04,610 --> 00:02:09,560
So if you just mention this to your interviewer, he or she will will be okay with that.

42
00:02:09,560 --> 00:02:10,430
So let's proceed.

43
00:02:10,430 --> 00:02:12,530
So we dequeue from the queue.

44
00:02:12,530 --> 00:02:15,470
Now let's swap the elements.

45
00:02:15,470 --> 00:02:15,800
All right.

46
00:02:15,800 --> 00:02:18,680
So we are at a particular node or a vertex.

47
00:02:18,680 --> 00:02:22,880
Now we are just going to swap the left and right of that particular node.

48
00:02:22,880 --> 00:02:24,110
So let's go ahead and do that.

49
00:02:24,110 --> 00:02:26,060
So we can say let temp.

50
00:02:26,060 --> 00:02:28,190
Let's use a temp with temporary variable.

51
00:02:28,190 --> 00:02:30,560
So let temp is equal to current dot right.

52
00:02:32,780 --> 00:02:36,650
And then we will say current dot right is equal to current dot left.

53
00:02:41,330 --> 00:02:41,840
All right.

54
00:02:41,840 --> 00:02:43,970
And then we will say current dot left.

55
00:02:45,200 --> 00:02:46,490
Is equal to temp.

56
00:02:46,490 --> 00:02:51,530
So we have swapped the left and right for that particular node.

57
00:02:51,530 --> 00:02:54,980
And then we will just check if there is a left node we will enqueue it.

58
00:02:54,980 --> 00:02:57,890
And if there is a right load right node we will enqueue it.

59
00:02:57,890 --> 00:03:02,270
So if current dot left in that case we will just say queue dot push.

60
00:03:03,140 --> 00:03:04,310
Current left.

61
00:03:07,180 --> 00:03:08,470
And if there is a right node.

62
00:03:08,470 --> 00:03:09,700
So if current dot nine.

63
00:03:09,730 --> 00:03:10,360
Right.

64
00:03:12,080 --> 00:03:14,270
Then we'll say Q dot push right.

65
00:03:14,270 --> 00:03:15,260
Current dot right.

66
00:03:20,000 --> 00:03:20,570
All right.

67
00:03:20,570 --> 00:03:21,920
So that's it.

68
00:03:21,920 --> 00:03:23,870
So this should do the work.

69
00:03:23,870 --> 00:03:24,200
All right.

70
00:03:24,200 --> 00:03:25,520
So what are we doing over here.

71
00:03:25,520 --> 00:03:28,790
We are going through the binary tree breadth first.

72
00:03:28,790 --> 00:03:31,010
So we're doing a breadth first traversal.

73
00:03:31,010 --> 00:03:34,880
And then at each node we are just swapping the left and the right.

74
00:03:34,880 --> 00:03:36,530
So this is what is happening over here.

75
00:03:36,530 --> 00:03:39,620
Now let's go ahead and call this function and test it.

76
00:03:39,620 --> 00:03:43,670
So over here again to test this we have our node and binary tree class.

77
00:03:43,670 --> 00:03:45,530
And we have the insert function over here.

78
00:03:45,530 --> 00:03:47,990
Using this we are creating a binary tree.

79
00:03:47,990 --> 00:03:51,350
And then we are inserting these values into the binary tree.

80
00:03:51,350 --> 00:03:53,300
Now let's just call this function.

81
00:03:53,300 --> 00:03:56,900
And let's see whether we are able to invert the given binary tree.

82
00:03:56,900 --> 00:04:00,050
So over here we have in invert iterative.

83
00:04:00,050 --> 00:04:01,790
And then we are going to pass the root.

84
00:04:01,790 --> 00:04:03,470
So that's tree dot root.

85
00:04:04,810 --> 00:04:09,670
All right, now, before we execute this, let me just draw this out so that we can check whether the

86
00:04:09,670 --> 00:04:11,890
tree has been successfully inverted.

87
00:04:13,260 --> 00:04:13,560
Right.

88
00:04:13,560 --> 00:04:15,390
So let's go ahead and draw this over here.

89
00:04:15,390 --> 00:04:17,850
So we have one which will be the root.

90
00:04:17,850 --> 00:04:19,200
Then we have two and three.

91
00:04:19,200 --> 00:04:21,870
So we have two and then we have three.

92
00:04:22,290 --> 00:04:24,960
And then we have four and null.

93
00:04:24,960 --> 00:04:27,780
So this is four and this will be null.

94
00:04:29,120 --> 00:04:32,240
And then we have null and five, so we have null.

95
00:04:32,900 --> 00:04:33,980
And five.

96
00:04:34,640 --> 00:04:36,260
And then we have six and null.

97
00:04:36,260 --> 00:04:37,760
So we have six over here.

98
00:04:37,760 --> 00:04:39,050
Null over here.

99
00:04:39,620 --> 00:04:41,390
And finally we have seven over here.

100
00:04:41,390 --> 00:04:43,580
So that would be this over here right.

101
00:04:43,580 --> 00:04:44,300
This is seven.

102
00:04:44,300 --> 00:04:48,980
So this is how the binary tree looks after we call the insert function.

103
00:04:48,980 --> 00:04:53,570
Now we are just going to call the insert function which is implemented iteratively.

104
00:04:53,570 --> 00:04:56,390
And we will pass the root which is this node over here.

105
00:04:56,390 --> 00:04:59,030
So let's go ahead and run our code.

106
00:05:05,240 --> 00:05:07,910
All right, now let's see what we are getting.

107
00:05:07,910 --> 00:05:10,370
And we are getting back the root.

108
00:05:10,370 --> 00:05:12,830
The root at this point is again one which is correct.

109
00:05:13,100 --> 00:05:15,320
And let me just open this up.

110
00:05:15,320 --> 00:05:16,700
So we have three and two.

111
00:05:16,730 --> 00:05:18,650
So yes these two have been swapped.

112
00:05:18,650 --> 00:05:18,830
Right.

113
00:05:18,830 --> 00:05:22,190
So let's parallelly write it over here so that we can visualize it.

114
00:05:24,280 --> 00:05:25,540
So we have one.

115
00:05:26,170 --> 00:05:28,030
So let me just write it over here.

116
00:05:28,030 --> 00:05:29,740
And then we have three and two.

117
00:05:31,580 --> 00:05:33,950
So yes, these two have been inverted right now.

118
00:05:33,950 --> 00:05:36,410
Let's proceed and open up the remaining part.

119
00:05:39,320 --> 00:05:41,960
So over here you can see the children of.

120
00:05:43,710 --> 00:05:44,970
This node, which is three.

121
00:05:44,970 --> 00:05:47,490
Write the children of three over here are.

122
00:05:48,680 --> 00:05:51,470
Five in the left part and right is null.

123
00:05:51,470 --> 00:05:52,730
So five is left.

124
00:05:52,730 --> 00:05:56,930
And let me just draw that over here five is left and the right is null.

125
00:05:57,170 --> 00:05:58,640
So that is correct right.

126
00:05:58,640 --> 00:06:00,500
So these two also have been inverted.

127
00:06:00,500 --> 00:06:02,540
And we have seen that these two have been inverted.

128
00:06:02,540 --> 00:06:03,800
So let's proceed.

129
00:06:04,250 --> 00:06:06,890
Now again let's open this up.

130
00:06:06,890 --> 00:06:12,350
So for five the children are left is null and right has value seven.

131
00:06:12,350 --> 00:06:14,330
So let me just draw that over here.

132
00:06:14,330 --> 00:06:17,690
So left is null and right has the value seven.

133
00:06:17,690 --> 00:06:20,000
So yes these two also have been inverted right.

134
00:06:20,000 --> 00:06:22,640
So this is null and this is also null.

135
00:06:22,640 --> 00:06:24,020
So these two also have been inverted.

136
00:06:24,020 --> 00:06:25,070
So that's also correct.

137
00:06:25,070 --> 00:06:26,210
So let's proceed.

138
00:06:26,210 --> 00:06:30,410
Now if you if you see for seven you will just get that both of them have null.

139
00:06:30,410 --> 00:06:32,720
So the children of seven will just be null.

140
00:06:32,720 --> 00:06:33,830
So that's also correct.

141
00:06:33,830 --> 00:06:35,150
Now let's proceed.

142
00:06:36,880 --> 00:06:39,790
Now let's try for the children of two.

143
00:06:39,790 --> 00:06:40,030
Right.

144
00:06:40,030 --> 00:06:41,320
So let's go to that level.

145
00:06:41,320 --> 00:06:42,310
Let's go back.

146
00:06:45,000 --> 00:06:46,140
So.

147
00:06:46,790 --> 00:06:47,930
Yes, this is true.

148
00:06:47,930 --> 00:06:48,350
Right.

149
00:06:48,350 --> 00:06:53,150
So for two the children the left is null and the right has value four.

150
00:06:53,150 --> 00:06:54,350
So let's draw that.

151
00:06:54,350 --> 00:06:55,700
So the left is null.

152
00:06:56,510 --> 00:06:58,370
And the right has value for.

153
00:06:58,700 --> 00:07:00,950
And you can see that these two have been inverted.

154
00:07:00,950 --> 00:07:02,330
So yes, this is also correct.

155
00:07:02,360 --> 00:07:04,910
Now let's look at the children of for.

156
00:07:07,150 --> 00:07:10,420
So you can see the left is null and the right has the value six.

157
00:07:10,750 --> 00:07:11,650
So let's draw that.

158
00:07:11,650 --> 00:07:13,000
So the left is null.

159
00:07:13,000 --> 00:07:14,290
The right has the value six.

160
00:07:14,290 --> 00:07:16,810
So yes these two also have been inverted.

161
00:07:16,810 --> 00:07:20,830
And if you just check the children of six you will just have null and null which is correct.

162
00:07:20,830 --> 00:07:22,390
So yes our function has worked.

163
00:07:22,390 --> 00:07:24,490
So this has been successfully inverted.

164
00:07:24,730 --> 00:07:29,890
Now let's go ahead and take a quick look at the space and time complexity of our solution.

165
00:07:30,460 --> 00:07:32,890
So for this let me just make clear this up.

166
00:07:32,890 --> 00:07:34,450
So we'll just clear this up.

167
00:07:36,170 --> 00:07:36,860
All right.

168
00:07:36,860 --> 00:07:42,110
So when it comes to the space and time complexity, first let's take a look at the time complexity.

169
00:07:42,110 --> 00:07:43,820
So here is our function.

170
00:07:43,820 --> 00:07:46,070
Now we can see that this is just breadth first search.

171
00:07:46,070 --> 00:07:46,370
Right.

172
00:07:46,370 --> 00:07:51,290
So we know that the time complexity of breadth first search is O of n because we are visiting every

173
00:07:51,290 --> 00:07:54,290
node once and then we are doing some constant time operations.

174
00:07:54,290 --> 00:07:58,940
Right, which is dequeuing and then swapping and then n queuing.

175
00:07:58,940 --> 00:07:59,090
Right.

176
00:07:59,090 --> 00:08:01,160
So these are just constant time operations.

177
00:08:01,160 --> 00:08:08,390
So this is happening for n times because every vertex, every node will be there in the queue at one

178
00:08:08,390 --> 00:08:09,290
point or the other.

179
00:08:09,290 --> 00:08:09,620
Right.

180
00:08:09,620 --> 00:08:13,580
So we will get everything into the queue because we are traversing through every node.

181
00:08:13,580 --> 00:08:16,700
So that's why the time complexity of this solution is O of n.

182
00:08:16,700 --> 00:08:18,800
And what about the space complexity?

183
00:08:18,800 --> 00:08:22,070
The space complexity also is going to be o of N right.

184
00:08:22,070 --> 00:08:22,670
Why is that?

185
00:08:22,670 --> 00:08:26,390
So the queue in the worst case can have n by two elements.

186
00:08:26,390 --> 00:08:31,010
For the case of a full binary tree where the leaves will have n by two elements, right.

187
00:08:31,010 --> 00:08:34,610
So we have seen that in previous videos where we have discussed this many times.

188
00:08:34,610 --> 00:08:36,260
So I'm not repeating it over here.

189
00:08:36,260 --> 00:08:37,790
And one by two is a constant.

190
00:08:37,790 --> 00:08:39,860
So we can just remove this and we get that.

191
00:08:39,860 --> 00:08:43,850
The space complexity also of this solution is equal to o of n.