1
00:00:00,730 --> 00:00:01,780
Welcome back.

2
00:00:01,780 --> 00:00:07,060
In this video, let's discuss how we can implement the level order traversal function.

3
00:00:07,060 --> 00:00:10,270
So let's say this is the binary tree which is given to us.

4
00:00:10,270 --> 00:00:16,660
And if we do a level order traversal of this binary tree the output should be this one over here.

5
00:00:16,660 --> 00:00:17,020
Right.

6
00:00:17,020 --> 00:00:19,210
Every level is made one array.

7
00:00:19,210 --> 00:00:19,900
So we have seven.

8
00:00:19,900 --> 00:00:22,690
Over here we have 11 comma one which is this level.

9
00:00:22,690 --> 00:00:25,300
And then we have 728 which is this.

10
00:00:25,300 --> 00:00:26,590
And then we have three.

11
00:00:26,590 --> 00:00:27,940
And then we have just five.

12
00:00:27,940 --> 00:00:29,740
So this is the level order traversal.

13
00:00:29,740 --> 00:00:31,450
So we are going level by level.

14
00:00:31,450 --> 00:00:34,540
And the elements in each level is made one array.

15
00:00:34,540 --> 00:00:36,280
And that's pushed to our output array.

16
00:00:36,280 --> 00:00:37,540
So this should be our output array.

17
00:00:37,540 --> 00:00:43,600
Now before we go ahead and discuss how we can write this or how we can make this an algorithm, how

18
00:00:43,600 --> 00:00:46,780
we can write this function, let's do a few observations.

19
00:00:46,900 --> 00:00:53,230
The first observation is if we just do breadth first search on this binary tree, what is it that we

20
00:00:53,230 --> 00:00:54,370
would be getting right?

21
00:00:54,370 --> 00:00:59,410
In that case we would get this array 711 1728, three and five.

22
00:00:59,410 --> 00:01:01,720
So you can see that it's the same order.

23
00:01:01,720 --> 00:01:04,300
The elements are in the same order right now.

24
00:01:04,300 --> 00:01:08,530
The only difference is that we have to split every level into an array.

25
00:01:08,530 --> 00:01:11,980
So for example this is one array 11 and one is a one array.

26
00:01:11,980 --> 00:01:15,910
Over here 728 is one array and three and five are separate arrays.

27
00:01:15,910 --> 00:01:24,310
So we just need to modify our breadth first search algorithm to have a mechanism whereby which we can

28
00:01:24,310 --> 00:01:26,410
make each level a separate array.

29
00:01:26,410 --> 00:01:28,180
So this is the first observation.

30
00:01:28,180 --> 00:01:28,630
All right.

31
00:01:28,660 --> 00:01:30,010
Now let's proceed.

32
00:01:30,400 --> 00:01:32,950
Now again let's say we start at the root node.

33
00:01:32,950 --> 00:01:34,090
So this is the root node.

34
00:01:34,090 --> 00:01:38,050
Now let's have our breadth first search algorithm over here.

35
00:01:38,050 --> 00:01:40,180
So there we just have a while loop right.

36
00:01:40,180 --> 00:01:41,710
While something is there in the queue.

37
00:01:41,710 --> 00:01:44,020
Initially we add the root node into our queue.

38
00:01:44,020 --> 00:01:47,230
And then while something is there in our queue we dequeue from the queue.

39
00:01:47,260 --> 00:01:49,990
We push to our output array if that is required.

40
00:01:49,990 --> 00:01:51,790
And then we enqueue the left and right.

41
00:01:51,790 --> 00:01:54,910
So this is how our typical breadth first search works.

42
00:01:54,910 --> 00:02:01,720
Right now let's think how we can modify this a little bit to make the output like this which is our

43
00:02:01,720 --> 00:02:02,920
level order traversal.

44
00:02:02,920 --> 00:02:09,340
Now for this to get some intuition before we start to go ahead and write the function and the solution.

45
00:02:09,340 --> 00:02:14,770
To get some intuition, let's just trace the queue during this process.

46
00:02:14,770 --> 00:02:15,130
All right.

47
00:02:15,130 --> 00:02:16,930
So we have our queue over here.

48
00:02:16,930 --> 00:02:19,870
Now initially we have our root node in our queue.

49
00:02:20,750 --> 00:02:24,110
Now, once we are inside this right, we will dequeue this.

50
00:02:24,110 --> 00:02:25,250
But I'm not removing it.

51
00:02:25,250 --> 00:02:26,360
I'm just keeping it there.

52
00:02:26,360 --> 00:02:27,470
We will dequeue this.

53
00:02:27,470 --> 00:02:27,860
All right.

54
00:02:28,130 --> 00:02:33,470
And then we will push the left and right of this queue this particular node into our queue.

55
00:02:33,470 --> 00:02:36,200
So in this case that's 11 and one which will happen over here.

56
00:02:36,200 --> 00:02:36,380
Right.

57
00:02:36,380 --> 00:02:40,160
We will enqueue the left and right of the current node which is 11 and one.

58
00:02:40,160 --> 00:02:47,570
And later when we take out 11 we will push its children right, which is seven at this point.

59
00:02:47,570 --> 00:02:52,880
And then when we dequeue one we will push its children, which is two and eight, into our queue.

60
00:02:52,880 --> 00:02:55,820
So this is how our queue proceeds right now.

61
00:02:55,820 --> 00:03:01,670
If we just can have a count variable, let's say we have a count variable and let's say we have a while

62
00:03:01,670 --> 00:03:02,180
loop.

63
00:03:02,180 --> 00:03:06,470
Such something like while count is less than q dot length.

64
00:03:06,470 --> 00:03:08,030
In that case this.

65
00:03:08,030 --> 00:03:11,240
We could use this to club the elements of a level together, right?

66
00:03:11,240 --> 00:03:16,190
For example, initially the queue just has one element and then the count is zero.

67
00:03:16,190 --> 00:03:21,140
Initially, let's say we have the count equal to zero initially, and the queue length is one at that

68
00:03:21,140 --> 00:03:21,530
point.

69
00:03:21,530 --> 00:03:24,200
So we will just have one element right.

70
00:03:24,200 --> 00:03:25,970
So while zero less than one.

71
00:03:25,970 --> 00:03:26,930
Yes that's true.

72
00:03:26,930 --> 00:03:28,370
So we get one element.

73
00:03:28,370 --> 00:03:30,290
And then let's say we increment the count.

74
00:03:30,290 --> 00:03:33,560
So we say count plus plus and count becomes one.

75
00:03:33,560 --> 00:03:33,770
Right.

76
00:03:33,770 --> 00:03:36,830
So we can just separate this out together.

77
00:03:36,830 --> 00:03:40,880
And which is what we want as per the output that we want right now.

78
00:03:40,880 --> 00:03:42,440
Let's say we are done with this.

79
00:03:42,440 --> 00:03:45,530
And we know that by this time we have enqueued these two elements.

80
00:03:45,530 --> 00:03:47,540
So the queue has these two elements, right.

81
00:03:47,540 --> 00:03:50,630
So the length at that point is going to be equal to two.

82
00:03:50,630 --> 00:03:52,580
And again count is zero right.

83
00:03:52,580 --> 00:03:56,390
So you can see that we can use this mechanism to get these two together.

84
00:03:56,390 --> 00:03:58,490
We get these two clubbed together right.

85
00:03:59,320 --> 00:04:01,420
Now what?

86
00:04:01,420 --> 00:04:01,960
After this?

87
00:04:01,960 --> 00:04:04,480
Like, let's say we are done with processing these two elements.

88
00:04:04,480 --> 00:04:09,640
So when we process this, we will be enqueuing seven and when we process this we will be Enqueuing two

89
00:04:09,640 --> 00:04:10,000
and eight.

90
00:04:10,000 --> 00:04:14,500
So once we are done with this right, once we are done with this, once we are out of this while loop,

91
00:04:14,500 --> 00:04:19,660
when count is equal to two, then at that point, right, what would be the length of the queue?

92
00:04:20,200 --> 00:04:21,010
The queue?

93
00:04:21,040 --> 00:04:23,680
The length of the queue at that point would be three, right.

94
00:04:23,680 --> 00:04:26,590
Because these three elements will be there in our queue.

95
00:04:26,590 --> 00:04:29,830
And yes, we can see it's these three elements that we want together.

96
00:04:29,830 --> 00:04:34,900
So this is the intuition that we have developed over here when we trace how the queue functions.

97
00:04:34,900 --> 00:04:35,200
Right.

98
00:04:35,200 --> 00:04:40,450
So we can see that if we just take the length of the queue and then if we have a count variable which

99
00:04:40,450 --> 00:04:43,930
is initially zero, and then we go up to the length of the queue, right.

100
00:04:43,930 --> 00:04:48,250
So using this we can club the elements at a particular level together.

101
00:04:48,250 --> 00:04:51,910
So this is how we are going to go ahead and solve this question.

102
00:04:51,910 --> 00:04:55,300
So let's try to implement this intuition into our function.

103
00:04:55,300 --> 00:04:59,890
So again over here we have our output array which is what we have to develop.

104
00:04:59,890 --> 00:05:01,600
And we start at the root node.

105
00:05:01,600 --> 00:05:04,150
And we have our while loop over here.

106
00:05:04,150 --> 00:05:05,620
And then we have our queue.

107
00:05:06,490 --> 00:05:12,640
Now this while loop is going to loop as long as there is something in the queue and initially, like

108
00:05:12,640 --> 00:05:17,200
in a typical breadth first search algorithm, we insert the root node into our queue.

109
00:05:17,230 --> 00:05:22,840
Now we calculate that the length is one, right, the length is one, and the count at this point is

110
00:05:22,840 --> 00:05:23,950
initialized to zero.

111
00:05:23,950 --> 00:05:25,660
And we will also need a variable.

112
00:05:25,660 --> 00:05:28,420
Let's call it car level which will be an empty array.

113
00:05:28,420 --> 00:05:33,340
And we are going to insert the values in the current level into this empty array.

114
00:05:33,340 --> 00:05:35,950
And then we will push this array to our output array.

115
00:05:35,950 --> 00:05:37,690
So this is how we are going to proceed.

116
00:05:37,690 --> 00:05:39,670
Now initially count is equal to zero.

117
00:05:39,670 --> 00:05:43,180
And the length of the queue at this point is equal to one.

118
00:05:43,180 --> 00:05:48,460
Now we are going to have the while loop which we discussed and while count less than length, we are

119
00:05:48,460 --> 00:05:53,830
going to do the operations that we typically do in a breadth first search operation, which is dequeue,

120
00:05:53,830 --> 00:05:56,740
push and enqueue the left and right elements.

121
00:05:56,740 --> 00:05:58,180
All right, the notes.

122
00:05:58,630 --> 00:06:03,520
The only difference over here is that we are not going to push to the output array, but rather we are

123
00:06:03,520 --> 00:06:04,930
going to push to car level.

124
00:06:04,930 --> 00:06:05,260
Right.

125
00:06:05,260 --> 00:06:08,950
This this variable over here, which is an empty array at this point.

126
00:06:08,950 --> 00:06:14,140
And then once we are out of this while loop, we will push car level to our output array.

127
00:06:14,140 --> 00:06:15,850
So this is how we will proceed.

128
00:06:15,850 --> 00:06:20,740
And then remember we need to loop as long as count is less than length.

129
00:06:20,740 --> 00:06:24,760
So after we are done with one pass we have to increment count over here.

130
00:06:24,760 --> 00:06:26,500
So we say count plus plus.

131
00:06:26,500 --> 00:06:27,010
All right.

132
00:06:27,040 --> 00:06:31,990
Now again and again as we discussed after we are out of this while loop, we will push car level to

133
00:06:31,990 --> 00:06:32,950
our output array.

134
00:06:32,980 --> 00:06:35,500
So this is the pseudocode of our algorithm.

135
00:06:35,500 --> 00:06:36,580
Now let's trace it.

136
00:06:36,580 --> 00:06:38,440
Initially the count is zero.

137
00:06:38,440 --> 00:06:39,340
Length is one.

138
00:06:39,340 --> 00:06:41,050
So yes zero is less than one.

139
00:06:41,050 --> 00:06:43,420
So we come inside and we dequeue.

140
00:06:43,420 --> 00:06:48,010
So we take out seven and we push it to our car level.

141
00:06:48,010 --> 00:06:50,140
So let's just have car level over here.

142
00:06:50,140 --> 00:06:53,170
Now this is going to be an array with just the element seven.

143
00:06:53,170 --> 00:06:55,240
And then we enqueue the left and right.

144
00:06:55,240 --> 00:06:57,100
So the left and right is 11 and one right.

145
00:06:57,100 --> 00:07:00,130
So we are going to enqueue 11 and one at these steps.

146
00:07:00,130 --> 00:07:01,780
And then we increment count.

147
00:07:01,780 --> 00:07:04,240
So count becomes equal to one.

148
00:07:04,240 --> 00:07:06,070
Now again we come and check over.

149
00:07:06,070 --> 00:07:07,360
Here is one less than one.

150
00:07:07,360 --> 00:07:08,410
No that's falsy.

151
00:07:08,410 --> 00:07:14,260
So we come out and at this line of code right at this place we are going to push car level which is

152
00:07:14,260 --> 00:07:16,270
just an array with one element seven.

153
00:07:16,270 --> 00:07:18,460
We are just going to push it to our output array.

154
00:07:18,460 --> 00:07:19,690
So we get this over here.

155
00:07:19,690 --> 00:07:20,290
All right.

156
00:07:20,290 --> 00:07:23,410
Now again we are going to come over here.

157
00:07:23,410 --> 00:07:25,300
Car level is going to be an empty array.

158
00:07:25,300 --> 00:07:32,530
And at this point uh again we will need to initialize or change our count to zero because at this point

159
00:07:32,530 --> 00:07:33,370
count became one.

160
00:07:33,370 --> 00:07:33,640
Right.

161
00:07:33,640 --> 00:07:36,310
So we make again the count equal to zero.

162
00:07:36,760 --> 00:07:38,410
And car level is an empty array.

163
00:07:38,410 --> 00:07:40,870
And the length the length over here is equal to two.

164
00:07:40,870 --> 00:07:41,050
Right.

165
00:07:41,050 --> 00:07:42,580
So we have to compute the length.

166
00:07:42,580 --> 00:07:44,890
The length of the queue at this point is equal to two.

167
00:07:44,920 --> 00:07:47,110
So let's change that and write two over here.

168
00:07:47,110 --> 00:07:48,100
So the length is two.

169
00:07:48,130 --> 00:07:49,840
Now zero is less than two.

170
00:07:49,870 --> 00:07:52,240
So we come inside the while loop we dequeue.

171
00:07:52,270 --> 00:07:58,030
That is we take out the 11 and we push it to our car level which just has 11 at this point.

172
00:07:58,030 --> 00:08:01,390
And we enqueue the left and right of 11, which is only seven.

173
00:08:01,390 --> 00:08:02,770
We don't enqueue the null.

174
00:08:02,770 --> 00:08:05,200
So we enqueue the seven over here.

175
00:08:05,200 --> 00:08:08,170
And then we are incrementing the count.

176
00:08:08,170 --> 00:08:09,460
So the count becomes one.

177
00:08:09,460 --> 00:08:10,000
All right.

178
00:08:10,000 --> 00:08:11,500
So the count becomes one.

179
00:08:11,500 --> 00:08:14,080
And then again we dequeue we dequeue.

180
00:08:14,080 --> 00:08:15,160
So the count is one.

181
00:08:15,160 --> 00:08:17,470
We'd queue and we took one.

182
00:08:17,470 --> 00:08:19,510
And we push it to our car level.

183
00:08:19,510 --> 00:08:22,600
So we get one over here and we enqueue the left and right.

184
00:08:22,600 --> 00:08:24,970
So the left is two and the right is eight.

185
00:08:24,970 --> 00:08:27,580
So two and eight get enqueued over here.

186
00:08:27,580 --> 00:08:29,890
And then we increment the count.

187
00:08:29,890 --> 00:08:31,240
So the count becomes two.

188
00:08:31,240 --> 00:08:33,190
Now two less than two is falsy.

189
00:08:33,190 --> 00:08:37,930
So we come out and we are going to push this car level into our output array.

190
00:08:37,930 --> 00:08:42,160
So we get 11 comma one which is an array over here to our output array.

191
00:08:42,310 --> 00:08:44,230
All right let's proceed again.

192
00:08:44,230 --> 00:08:45,700
We change count to zero.

193
00:08:45,700 --> 00:08:50,080
And the length of the queue at this point is equal to three.

194
00:08:50,080 --> 00:08:51,550
So we change this to three.

195
00:08:51,550 --> 00:08:52,840
So we have the length three.

196
00:08:52,840 --> 00:08:53,830
The count is zero.

197
00:08:53,830 --> 00:08:57,220
And car level is again an empty array now zero less than three.

198
00:08:57,220 --> 00:09:01,480
So we come inside we dequeue and then we push it to our car level.

199
00:09:01,480 --> 00:09:03,760
And again we come over here.

200
00:09:03,760 --> 00:09:05,320
We check its left and right.

201
00:09:05,320 --> 00:09:07,480
We don't have anything to enqueue at this point right.

202
00:09:07,480 --> 00:09:09,430
Because its left and right are null.

203
00:09:09,430 --> 00:09:12,430
Over here again we increment count.

204
00:09:12,430 --> 00:09:13,660
So count becomes one.

205
00:09:13,660 --> 00:09:15,100
One is less than three.

206
00:09:15,100 --> 00:09:17,230
Again we come inside VDC two.

207
00:09:17,260 --> 00:09:21,730
We push it to car level and its children three this is null.

208
00:09:21,730 --> 00:09:23,260
So null does not get enqueued.

209
00:09:23,260 --> 00:09:25,420
But three over here gets enqueued.

210
00:09:25,420 --> 00:09:25,810
All right.

211
00:09:25,810 --> 00:09:27,010
And we increment count.

212
00:09:27,010 --> 00:09:28,060
So count is equal to two.

213
00:09:28,090 --> 00:09:29,140
Two is less than three.

214
00:09:29,140 --> 00:09:31,150
So again we come inside VDC.

215
00:09:31,180 --> 00:09:36,190
That is we take the eight and we push it to car level and its left and right which is null.

216
00:09:36,190 --> 00:09:39,190
So we don't have anything to enqueue at this point.

217
00:09:39,190 --> 00:09:41,440
And count is again incremented to three.

218
00:09:41,440 --> 00:09:43,090
Now three less than three is falsy.

219
00:09:43,090 --> 00:09:48,190
So we come out of the while loop this one over here and we are going to push car level to our output

220
00:09:48,190 --> 00:09:52,720
array, which is this array over here with three elements seven, two and eight.

221
00:09:52,990 --> 00:09:53,530
All right.

222
00:09:53,530 --> 00:09:57,520
Now again we come and we are we are again over here right.

223
00:09:57,520 --> 00:09:59,410
So again count is changed to zero.

224
00:09:59,410 --> 00:10:02,410
And the length at this point is equal to one.

225
00:10:02,410 --> 00:10:04,060
The length of the queue is equal to one.

226
00:10:04,060 --> 00:10:06,070
So we change that and then car level is.

227
00:10:06,200 --> 00:10:07,250
Again, an empty array.

228
00:10:07,280 --> 00:10:09,560
Now zero less than one, which is truthy.

229
00:10:09,590 --> 00:10:11,450
So we come inside, we dequeue.

230
00:10:11,450 --> 00:10:14,330
So we take the three and we push it to our care level.

231
00:10:14,330 --> 00:10:16,730
And its children, which is five only.

232
00:10:16,730 --> 00:10:17,000
Right.

233
00:10:17,000 --> 00:10:18,350
It just has one child five.

234
00:10:18,350 --> 00:10:21,770
So that gets enqueued and count is incremented to one.

235
00:10:21,770 --> 00:10:23,570
Now one less than one is falsy.

236
00:10:23,570 --> 00:10:29,330
So we come out and we push this this care level three into our output array.

237
00:10:29,480 --> 00:10:32,630
Again we come over here count is changed to zero.

238
00:10:32,630 --> 00:10:34,310
Right count is changed to zero.

239
00:10:35,070 --> 00:10:37,560
And the length at this point is again one.

240
00:10:37,560 --> 00:10:42,180
So it's one only now we we see that zero less than one is true.

241
00:10:42,180 --> 00:10:48,420
Three we come inside VDC this five and we push it to our car level and then its children.

242
00:10:48,420 --> 00:10:50,550
It does not have any children, nothing to NQ.

243
00:10:50,550 --> 00:10:52,320
And then we increment count.

244
00:10:52,320 --> 00:10:54,870
So one and then one less than one is false.

245
00:10:54,870 --> 00:11:01,890
So we come over here and at this point we push this to our output array which is the array with just

246
00:11:01,890 --> 00:11:02,820
one element five.

247
00:11:02,820 --> 00:11:04,740
So this is how this function works.

248
00:11:04,740 --> 00:11:08,910
And this is how we get our output array which is the level order traversal.

249
00:11:08,910 --> 00:11:11,580
So every level is made into one element.

250
00:11:11,580 --> 00:11:12,600
So we have seven.

251
00:11:12,600 --> 00:11:15,210
Then we have 11 17283.

252
00:11:15,210 --> 00:11:16,260
And then we have five.

253
00:11:16,260 --> 00:11:18,210
So this is how this algorithm works.

254
00:11:18,210 --> 00:11:23,370
Now let's discuss the complexity analysis of this solution which we just now discussed.

255
00:11:23,370 --> 00:11:28,710
The time complexity of this solution is going to be of the order of n, where n is the number of elements

256
00:11:28,710 --> 00:11:29,940
in our binary tree.

257
00:11:29,940 --> 00:11:30,600
Why is that?

258
00:11:30,600 --> 00:11:33,450
So we are visiting every node one time right.

259
00:11:33,450 --> 00:11:36,420
So you can see that we are visiting every node one time.

260
00:11:36,420 --> 00:11:37,770
So that is happening over here.

261
00:11:37,770 --> 00:11:37,950
Right?

262
00:11:37,950 --> 00:11:44,250
This while loop over here will execute n number of times where n is the number of nodes in our binary

263
00:11:44,250 --> 00:11:44,820
tree.

264
00:11:44,880 --> 00:11:45,330
Right.

265
00:11:45,330 --> 00:11:49,020
Because we are going to dequeue and we are going to push into car level.

266
00:11:49,020 --> 00:11:53,970
And you can see that every value over here in the binary tree is there in some element or the other

267
00:11:53,970 --> 00:11:54,510
over here.

268
00:11:54,510 --> 00:11:57,180
So that's why this will operate n number of times.

269
00:11:57,180 --> 00:11:57,510
Right.

270
00:11:57,510 --> 00:12:00,420
For one time for every element in our binary tree.

271
00:12:00,420 --> 00:12:02,400
So we are doing n operations over here.

272
00:12:03,310 --> 00:12:05,140
And then we have a while loop over here.

273
00:12:05,140 --> 00:12:05,440
Right.

274
00:12:05,440 --> 00:12:07,300
You can see we have this while loop over here.

275
00:12:07,300 --> 00:12:12,310
This while loop is going to do number of operations which is equal to the number of levels.

276
00:12:12,310 --> 00:12:12,760
Right.

277
00:12:12,760 --> 00:12:17,470
Because this takes care that the elements in one level are clubbed together.

278
00:12:17,470 --> 00:12:25,150
So it will do 123455 operations for this binary tree over here because it has five levels.

279
00:12:25,150 --> 00:12:25,450
Right.

280
00:12:25,450 --> 00:12:28,630
So this is going to do operations equal to the number of levels.

281
00:12:28,630 --> 00:12:34,300
But because we can be sure that n is greater than the number of levels, we can just say that the time

282
00:12:34,300 --> 00:12:36,640
complexity is of the order of n.

283
00:12:36,640 --> 00:12:39,790
Or we can say it's of the order of n plus number of levels.

284
00:12:39,790 --> 00:12:44,980
But again, because n is greater than number of levels, we can just ignore this because this will dominate.

285
00:12:44,980 --> 00:12:49,090
And that's why we can say that the time complexity is of the order of n.

286
00:12:49,090 --> 00:12:51,250
Now what about the space complexity?

287
00:12:52,130 --> 00:12:52,640
For this.

288
00:12:52,640 --> 00:12:58,820
Let's think about what are the things in our algorithm that takes up space, that can scale when the

289
00:12:58,820 --> 00:13:01,670
input scales, right when the input n increases.

290
00:13:01,670 --> 00:13:03,800
So we have our queue which we are using.

291
00:13:03,800 --> 00:13:05,660
And then we have our output array.

292
00:13:05,690 --> 00:13:08,780
Now the output array is going to have every element right.

293
00:13:08,780 --> 00:13:10,910
Every element has to be there in our output array.

294
00:13:10,910 --> 00:13:16,250
So that's why we can clearly see that the output array is going to take space of the order of n.

295
00:13:16,250 --> 00:13:18,560
So this is going to be o of n space.

296
00:13:18,560 --> 00:13:20,870
Now what about the queue for this.

297
00:13:20,870 --> 00:13:22,700
Again because this is a big O analysis.

298
00:13:22,700 --> 00:13:25,730
Let's think about the worst case of the queue.

299
00:13:25,730 --> 00:13:27,290
Now when will this happen?

300
00:13:27,290 --> 00:13:33,770
If we are having a full binary tree in the last level we have previously seen, there will be elements

301
00:13:33,770 --> 00:13:35,420
of the order of n by two, right?

302
00:13:35,420 --> 00:13:39,470
For example, over here you can see we have 15 elements.

303
00:13:39,470 --> 00:13:40,730
So this is eight.

304
00:13:40,730 --> 00:13:44,960
So exactly this eight would be equal to n plus one by two.

305
00:13:44,960 --> 00:13:45,440
Right.

306
00:13:45,440 --> 00:13:47,870
So that's approximately n by two right.

307
00:13:47,870 --> 00:13:50,060
So approximately n by two elements.

308
00:13:50,060 --> 00:13:51,770
Or we have eight elements over here.

309
00:13:51,950 --> 00:13:54,770
Or again we are seeing off the order of n by two elements.

310
00:13:55,690 --> 00:13:55,930
Again.

311
00:13:55,930 --> 00:13:56,950
I'm just writing it over here.

312
00:13:56,950 --> 00:13:57,430
Exactly.

313
00:13:57,430 --> 00:14:01,570
We can say it's n plus one by two elements, but then these are just constants, right?

314
00:14:01,570 --> 00:14:04,900
So that's why I can say it's of the order of n by two elements.

315
00:14:04,900 --> 00:14:10,600
So we can say that the space complexity of the queue in the worst case will be of the order of n by

316
00:14:10,600 --> 00:14:10,870
two.

317
00:14:10,900 --> 00:14:11,860
Why is that so.

318
00:14:11,860 --> 00:14:16,840
Because you can see when we are processing this level, right, we are going to dequeue this particular

319
00:14:16,840 --> 00:14:18,580
node and we will enqueue these two.

320
00:14:18,610 --> 00:14:20,080
Then we will dequeue this one.

321
00:14:20,080 --> 00:14:21,280
We will enqueue these two.

322
00:14:21,310 --> 00:14:22,570
We will dequeue this one.

323
00:14:22,570 --> 00:14:23,770
We will enqueue these two.

324
00:14:23,800 --> 00:14:25,930
We will dequeue this one and we will enqueue these two.

325
00:14:25,930 --> 00:14:30,280
So at that instance all these eight nodes are going to be there in our queue.

326
00:14:30,280 --> 00:14:30,580
Right.

327
00:14:30,580 --> 00:14:36,790
So that's why we can say the worst case space complexity of the queue is going to be of the order of

328
00:14:36,790 --> 00:14:37,540
n by two.

329
00:14:37,540 --> 00:14:40,300
And because this is just a constant, this one by two.

330
00:14:40,300 --> 00:14:40,600
Right.

331
00:14:40,600 --> 00:14:41,890
We can just avoid that.

332
00:14:41,890 --> 00:14:42,070
Right.

333
00:14:42,070 --> 00:14:43,390
So we can just avoid that.

334
00:14:43,390 --> 00:14:48,490
And that's why we can say that the space complexity is also of the order of n.

335
00:14:48,490 --> 00:14:51,190
So the time complexity is of the order of n.

336
00:14:51,190 --> 00:14:55,090
And the space complexity of a solution is of the order of n.