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

2
00:00:01,660 --> 00:00:07,000
Let's now go ahead and write the level order traversal function that we just now discussed.

3
00:00:07,000 --> 00:00:09,880
So over here I have our node class.

4
00:00:09,880 --> 00:00:11,890
Then I have our binary tree class.

5
00:00:11,890 --> 00:00:15,430
And we have already discussed the insert function which we have written together.

6
00:00:15,430 --> 00:00:17,440
So this array has been passed to it.

7
00:00:17,440 --> 00:00:19,600
And we have already created our binary tree.

8
00:00:19,600 --> 00:00:23,950
Now we will go ahead and write the function which will take in the root of this tree.

9
00:00:23,950 --> 00:00:26,770
And we will traverse this tree level order.

10
00:00:26,770 --> 00:00:30,700
So let's go ahead and write this function and let's call it level order traversal.

11
00:00:34,780 --> 00:00:35,350
All right.

12
00:00:35,350 --> 00:00:40,600
Now this function is going to take in the root of the tree.

13
00:00:42,080 --> 00:00:42,470
All right.

14
00:00:42,500 --> 00:00:46,880
Now, once you're inside this function, we will just check if the root is null.

15
00:00:46,880 --> 00:00:50,390
So if not root, then we will just return an empty array.

16
00:00:52,480 --> 00:00:54,820
Now, if this is not the case, we proceed.

17
00:00:54,820 --> 00:00:56,650
So let's have a variable.

18
00:00:56,650 --> 00:00:57,880
Let's call it output.

19
00:00:58,680 --> 00:01:00,660
So this is going to be an empty array.

20
00:01:01,050 --> 00:01:04,290
And we will traverse this tree which is given to us.

21
00:01:04,290 --> 00:01:06,720
And we will fill in the arrays, the levels.

22
00:01:06,720 --> 00:01:06,930
Right.

23
00:01:06,930 --> 00:01:08,250
One level will be one array.

24
00:01:08,250 --> 00:01:10,230
We will fill those arrays to this output array.

25
00:01:10,230 --> 00:01:12,840
And finally we will just return this output array.

26
00:01:13,920 --> 00:01:15,600
So this is how we will proceed.

27
00:01:15,600 --> 00:01:18,210
And we also need q a q.

28
00:01:18,210 --> 00:01:18,420
Right.

29
00:01:18,420 --> 00:01:19,890
So let's say const q.

30
00:01:19,890 --> 00:01:23,250
And initially we will fill the root into this array.

31
00:01:23,250 --> 00:01:25,860
Now over here we are implementing the Q as an array.

32
00:01:25,860 --> 00:01:31,800
But ideally to get a optimum time complexity when you are taking out L because we will be taking out

33
00:01:31,800 --> 00:01:33,330
elements from the beginning of the queue.

34
00:01:33,330 --> 00:01:38,460
So you have to use a linked list to implement this queue, because in JavaScript there is no inbuilt

35
00:01:38,460 --> 00:01:40,980
queue data structure, but over here it's fine.

36
00:01:40,980 --> 00:01:45,330
Typically in an interview to save time we will use an array when we implement a queue.

37
00:01:45,330 --> 00:01:49,890
But be sure that you mention this to your interviewer and mostly they will be okay, because that's

38
00:01:49,890 --> 00:01:51,570
not the central question over here.

39
00:01:51,570 --> 00:01:53,760
The central question is level order traversal.

40
00:01:53,760 --> 00:01:54,930
So let's proceed.

41
00:01:54,930 --> 00:01:58,530
Now we have inserted the root to the queue and then we will have a while loop.

42
00:01:58,530 --> 00:02:01,740
And this will loop as long as something is there in the queue.

43
00:02:01,740 --> 00:02:03,030
So while queue dot length.

44
00:02:03,030 --> 00:02:06,600
So this is what we have seen in the case of breadth first search the same thing.

45
00:02:06,600 --> 00:02:07,920
So while queue dot length.

46
00:02:07,920 --> 00:02:09,720
And then we will have our loop over here.

47
00:02:09,720 --> 00:02:13,650
Now again as we discussed in the previous video, we will make some changes over here.

48
00:02:13,650 --> 00:02:18,810
Now initially once we are inside this loop let's identify the length of the queue at this point.

49
00:02:18,810 --> 00:02:22,200
So let length is equal to q dot length.

50
00:02:24,000 --> 00:02:25,380
And then we will have a counter.

51
00:02:25,380 --> 00:02:29,100
So let's say let count is equal to zero.

52
00:02:29,130 --> 00:02:31,800
Now we will have one more while loop over here.

53
00:02:31,800 --> 00:02:36,960
And this will go on looping as long as count is less than length.

54
00:02:37,920 --> 00:02:42,840
Now it is here that we will develop or build each current level value, which will be an array.

55
00:02:42,840 --> 00:02:48,210
And once we are out of this while loop, we will push it to the output array which we created over here.

56
00:02:48,360 --> 00:02:48,900
All right.

57
00:02:48,900 --> 00:02:54,870
So once we are inside this while loop let's shift the first or dequeue the first element from the queue.

58
00:02:54,870 --> 00:03:00,300
So we can say const cur which is the current element is equal to q dot shift.

59
00:03:02,130 --> 00:03:06,540
So we take out the first element from the queue and then we will push it to the current level.

60
00:03:06,540 --> 00:03:06,900
All right.

61
00:03:06,900 --> 00:03:08,910
So for this we will need the current level.

62
00:03:08,910 --> 00:03:10,560
So again let's create that over here.

63
00:03:10,560 --> 00:03:14,820
So initially let let's say current level at this point is an empty array.

64
00:03:14,820 --> 00:03:15,660
So const.

65
00:03:16,970 --> 00:03:17,450
Car.

66
00:03:17,450 --> 00:03:19,490
Let's just call it car level.

67
00:03:20,270 --> 00:03:22,250
Values or.

68
00:03:22,250 --> 00:03:23,210
Yeah values.

69
00:03:23,210 --> 00:03:24,680
So that is an empty array.

70
00:03:24,710 --> 00:03:25,160
All right.

71
00:03:25,160 --> 00:03:29,930
So again whenever we come back over here it will be a new level.

72
00:03:29,930 --> 00:03:30,140
Right.

73
00:03:30,140 --> 00:03:32,420
So again we make it empty at this point.

74
00:03:32,420 --> 00:03:37,370
So once we are inside this while loop we will just push this curve to the current level values.

75
00:03:37,370 --> 00:03:40,040
So we can say for level values.

76
00:03:41,470 --> 00:03:42,490
Dot push.

77
00:03:43,380 --> 00:03:46,440
And then, as per the question, we only want the value of the node, right?

78
00:03:46,440 --> 00:03:50,610
So we can say cur dot value at this point.

79
00:03:51,030 --> 00:03:55,680
So we are pushing the value of the current node to the uh cur level value array.

80
00:03:57,020 --> 00:04:02,510
Now what we will do is we will check if there is something to the left of the current node and if it

81
00:04:02,510 --> 00:04:04,160
is there, we will push it to the queue.

82
00:04:04,160 --> 00:04:06,290
And again we will do the same thing for the right.

83
00:04:06,290 --> 00:04:08,660
So this is what we have seen always in breadth first search.

84
00:04:08,660 --> 00:04:10,640
So the same thing is what we're doing over here.

85
00:04:10,640 --> 00:04:11,600
Now let's continue.

86
00:04:11,600 --> 00:04:12,440
So if.

87
00:04:13,200 --> 00:04:13,980
Current.

88
00:04:15,530 --> 00:04:16,790
Dot left.

89
00:04:17,150 --> 00:04:22,700
So if there is a node to the left of the current node, again this is curved, so curved or left.

90
00:04:22,700 --> 00:04:26,090
So if curved or left then we will push it to the queue.

91
00:04:26,090 --> 00:04:27,530
So we say queue dot push.

92
00:04:28,880 --> 00:04:29,780
Car dot left.

93
00:04:32,860 --> 00:04:34,090
And we do the same thing for.

94
00:04:34,090 --> 00:04:34,390
Right.

95
00:04:34,390 --> 00:04:36,850
So if car dot right.

96
00:04:38,380 --> 00:04:41,140
We push it to the q so q dot push.

97
00:04:42,230 --> 00:04:42,740
Car dot.

98
00:04:42,740 --> 00:04:43,310
Right.

99
00:04:45,050 --> 00:04:45,500
All right.

100
00:04:45,500 --> 00:04:49,640
And then we just have to increment the count so we can say count plus plus.

101
00:04:51,480 --> 00:04:57,630
So this will go on looping as long as count is less than length and it will come out when count is equal

102
00:04:57,630 --> 00:04:58,260
to length, right?

103
00:04:58,260 --> 00:05:00,810
So at that point we will just push to the output array.

104
00:05:00,810 --> 00:05:02,310
So we say output dot push.

105
00:05:03,380 --> 00:05:06,140
The core level values.

106
00:05:06,140 --> 00:05:07,220
And this will be an array.

107
00:05:07,220 --> 00:05:09,680
So this array is pushed into the output array.

108
00:05:09,740 --> 00:05:10,670
And that's it.

109
00:05:10,670 --> 00:05:14,780
And once we are out of this while loop we will have gone through every level.

110
00:05:14,780 --> 00:05:16,940
And then we have to just return the output.

111
00:05:16,940 --> 00:05:18,980
So let's go ahead and test this.

112
00:05:18,980 --> 00:05:21,890
So we have our binary tree over here.

113
00:05:21,890 --> 00:05:23,900
Let's just quickly draw it out together.

114
00:05:23,900 --> 00:05:29,090
And then we will see whether when we call the level order traversal function whether we are getting

115
00:05:29,090 --> 00:05:30,290
the correct output.

116
00:05:30,290 --> 00:05:31,610
So let's just check that out.

117
00:05:32,700 --> 00:05:33,060
All right.

118
00:05:33,060 --> 00:05:35,700
So I have drawn the binary tree over here.

119
00:05:35,700 --> 00:05:37,920
Now let's call the function.

120
00:05:37,920 --> 00:05:39,360
So level order traversal.

121
00:05:39,360 --> 00:05:43,650
And we will be passing the root of this binary tree to this function.

122
00:05:43,650 --> 00:05:46,950
So we say tree dot root we pass tree dot root.

123
00:05:49,620 --> 00:05:51,330
All right, so let's run our code.

124
00:05:52,250 --> 00:05:53,990
And let's take a look at the output.

125
00:05:53,990 --> 00:05:55,790
So we are getting an array of arrays.

126
00:05:55,790 --> 00:05:57,080
So that's correct.

127
00:05:57,080 --> 00:05:58,010
So let's take a look.

128
00:05:58,010 --> 00:06:00,830
So the first element is seven which is this one over here.

129
00:06:00,830 --> 00:06:03,530
And then we have 11 comma one which is this level.

130
00:06:03,530 --> 00:06:06,110
Then we have 728 which is this level.

131
00:06:06,110 --> 00:06:07,160
And then we have three.

132
00:06:07,160 --> 00:06:08,180
And then we have five.

133
00:06:08,180 --> 00:06:10,070
So yes our function is working.

134
00:06:10,070 --> 00:06:13,760
Now let's try to walk through the code and see what's happening.

135
00:06:14,590 --> 00:06:16,180
So here is our function.

136
00:06:16,180 --> 00:06:18,460
And this is the binary tree which we have.

137
00:06:18,460 --> 00:06:22,390
Now let's say the root which is seven is past and we are inside this function.

138
00:06:22,390 --> 00:06:25,780
So let's take a look at the code and walk through what's happening over here.

139
00:06:25,780 --> 00:06:27,880
Now first we come over here right.

140
00:06:27,880 --> 00:06:31,000
So when we are over here we see that the root is not null.

141
00:06:31,000 --> 00:06:34,780
So we come over here and output at this point is empty is an empty array.

142
00:06:34,930 --> 00:06:36,670
So let's just have output over here.

143
00:06:36,670 --> 00:06:37,930
This is an empty array.

144
00:06:38,410 --> 00:06:40,420
And then we come over here we have the queue.

145
00:06:40,420 --> 00:06:42,520
So let's just have the queue also over here.

146
00:06:43,370 --> 00:06:46,250
And at this point we put the route into the queue.

147
00:06:46,250 --> 00:06:47,900
So we have seven inside the queue.

148
00:06:47,930 --> 00:06:51,320
Then we come over here, we see that there is something in the queue, right.

149
00:06:51,320 --> 00:06:54,980
So we come over here and the length we identify the length is equal to one.

150
00:06:54,980 --> 00:06:57,650
Now we make count as zero initially.

151
00:06:57,650 --> 00:07:01,010
And then we have car level values which is an empty array.

152
00:07:01,520 --> 00:07:01,940
All right.

153
00:07:01,940 --> 00:07:04,820
So we go we are going to this while loop.

154
00:07:04,820 --> 00:07:07,370
And this will loop as long as count is less than length.

155
00:07:07,370 --> 00:07:08,390
So count is zero.

156
00:07:08,390 --> 00:07:09,350
Zero is less than one.

157
00:07:09,350 --> 00:07:10,430
So we come inside.

158
00:07:10,430 --> 00:07:11,930
We shift from the queue.

159
00:07:11,930 --> 00:07:13,340
So we get seven right.

160
00:07:13,340 --> 00:07:17,600
So this node is taken out and then we push it to car level values.

161
00:07:17,600 --> 00:07:19,940
The value of this particular node which is seven.

162
00:07:19,940 --> 00:07:21,230
So we get seven over here.

163
00:07:21,230 --> 00:07:24,230
And then its left is n cubed which is 11.

164
00:07:24,230 --> 00:07:25,670
So we put 11 over here.

165
00:07:25,670 --> 00:07:28,280
And then its right which is one that is also n cubed.

166
00:07:28,280 --> 00:07:30,860
We get one also over here and we increment count.

167
00:07:30,860 --> 00:07:33,920
So count becomes one and now one less than one.

168
00:07:33,920 --> 00:07:34,550
This is false.

169
00:07:34,640 --> 00:07:36,560
So we come out of this while loop.

170
00:07:36,560 --> 00:07:42,440
And then at this line we are going to push car level values which is this array over here into the output

171
00:07:42,440 --> 00:07:42,650
array.

172
00:07:42,650 --> 00:07:44,000
So we get seven over here.

173
00:07:44,960 --> 00:07:45,380
All right.

174
00:07:45,380 --> 00:07:51,140
So once that is done, we again come over here and we come inside the while loop because we have two

175
00:07:51,140 --> 00:07:52,280
elements inside the queue.

176
00:07:52,280 --> 00:07:53,600
So the queue is not empty.

177
00:07:53,630 --> 00:07:57,200
So again the length is now calculated which is two at this point.

178
00:07:57,200 --> 00:07:58,460
So this is equal to two.

179
00:07:58,460 --> 00:08:00,290
And count is changed to zero.

180
00:08:00,290 --> 00:08:01,310
So count is zero.

181
00:08:01,310 --> 00:08:04,430
And then car level values is an empty array at this point again.

182
00:08:04,430 --> 00:08:06,320
And then zero is less than two.

183
00:08:06,320 --> 00:08:07,310
So we come inside.

184
00:08:07,310 --> 00:08:07,820
We shift.

185
00:08:07,820 --> 00:08:12,230
So we take 11 out and we push it to the car level values array.

186
00:08:12,230 --> 00:08:14,360
Over here the value 11 is pushed over here.

187
00:08:14,360 --> 00:08:16,100
And then it's left and right.

188
00:08:16,100 --> 00:08:17,570
So it's left is null.

189
00:08:17,570 --> 00:08:19,850
So uh that is this is false.

190
00:08:19,850 --> 00:08:23,420
So we don't push uh null to the uh, queue.

191
00:08:23,420 --> 00:08:25,550
But when we come over here this is truthy.

192
00:08:25,580 --> 00:08:25,790
Right.

193
00:08:25,790 --> 00:08:27,260
So there is a node over here.

194
00:08:27,260 --> 00:08:28,850
So seven is pushed to the queue.

195
00:08:28,850 --> 00:08:31,400
So we get seven over here and count is incremented.

196
00:08:31,400 --> 00:08:32,630
So count becomes one.

197
00:08:32,630 --> 00:08:34,100
So again one is less than two.

198
00:08:34,100 --> 00:08:35,390
So we come again inside.

199
00:08:35,390 --> 00:08:35,960
We shift.

200
00:08:35,960 --> 00:08:37,250
So we take one out.

201
00:08:37,250 --> 00:08:39,470
And we put that to car level values.

202
00:08:39,470 --> 00:08:41,570
Over here we push it to car level values.

203
00:08:41,570 --> 00:08:44,270
And then it's left and right which is two and eight.

204
00:08:44,270 --> 00:08:48,320
Get enqueued so we get two and eight over here and count is incremented.

205
00:08:48,320 --> 00:08:50,090
Now two is not less than two.

206
00:08:50,120 --> 00:08:55,160
So we come out of this and this over here this array 11 comma one is pushed to the output array.

207
00:08:55,160 --> 00:08:58,280
So we get 11 and one over here 11 comma one over here.

208
00:08:58,280 --> 00:08:58,880
All right.

209
00:08:58,880 --> 00:09:01,220
Now let me just clear this up a bit.

210
00:09:04,680 --> 00:09:07,200
So in our queue we have seven, two, eight.

211
00:09:07,200 --> 00:09:09,000
And again we come over here.

212
00:09:09,000 --> 00:09:10,860
Length is now calculated.

213
00:09:10,860 --> 00:09:12,900
It's equal to three right.

214
00:09:12,900 --> 00:09:14,370
So let me just clear this up.

215
00:09:14,370 --> 00:09:15,810
So length is equal to three.

216
00:09:15,810 --> 00:09:18,750
And the count is again initialized to zero.

217
00:09:18,750 --> 00:09:21,750
And car level values is empty is an empty array at this point.

218
00:09:21,750 --> 00:09:22,920
Now zero less than three.

219
00:09:22,920 --> 00:09:24,720
So we come inside VDC.

220
00:09:24,750 --> 00:09:29,250
We take out seven and we push it to the car level values array over here.

221
00:09:29,250 --> 00:09:31,590
And then it's left and right which is null right.

222
00:09:31,590 --> 00:09:32,640
So these two are null.

223
00:09:32,640 --> 00:09:34,590
So nothing gets n cubed over here.

224
00:09:34,590 --> 00:09:36,870
And count is incremented at this point.

225
00:09:36,870 --> 00:09:38,310
Again one is less than three.

226
00:09:38,310 --> 00:09:41,490
So VDC and we push it to car level value.

227
00:09:41,490 --> 00:09:44,190
So we get two over here and then it's left and right.

228
00:09:44,190 --> 00:09:45,450
So it's left is null.

229
00:09:45,450 --> 00:09:46,680
It's right is three.

230
00:09:46,680 --> 00:09:48,300
So three gets added over here.

231
00:09:49,080 --> 00:09:51,330
And then car the count is incremented.

232
00:09:51,330 --> 00:09:52,080
So we have two.

233
00:09:52,110 --> 00:09:53,610
Two is two is less than three.

234
00:09:53,610 --> 00:09:55,350
So again eight is dequeued.

235
00:09:55,350 --> 00:09:58,020
And we push it to the car level values array over here.

236
00:09:58,020 --> 00:10:01,470
And at this point count will be incremented to three.

237
00:10:01,470 --> 00:10:03,150
Now three is not less than three.

238
00:10:03,150 --> 00:10:06,450
So we come out and this over here is pushed to our output array.

239
00:10:06,450 --> 00:10:08,760
So we get 728 over here.

240
00:10:09,890 --> 00:10:13,370
All right, so that's how we got to that place.

241
00:10:13,370 --> 00:10:18,650
So let's just get this back and just going to make some space over here.

242
00:10:18,650 --> 00:10:21,110
Now in our queue we just have three right.

243
00:10:21,110 --> 00:10:24,080
So again when we come over here the queue is not empty.

244
00:10:24,110 --> 00:10:24,290
Right.

245
00:10:24,290 --> 00:10:25,580
So we come inside.

246
00:10:25,610 --> 00:10:28,310
Now the queues length is one.

247
00:10:28,310 --> 00:10:30,440
The count is again initialized to zero.

248
00:10:30,440 --> 00:10:34,580
And kernel level values again is an empty array at this point right over here.

249
00:10:34,940 --> 00:10:38,870
And we are now going to come inside the loop because zero is less than one.

250
00:10:38,870 --> 00:10:40,100
Now we're going to shift.

251
00:10:40,100 --> 00:10:41,210
So we take out three.

252
00:10:41,240 --> 00:10:42,890
We put it to car level values.

253
00:10:42,890 --> 00:10:44,330
We push it to car level values.

254
00:10:44,330 --> 00:10:45,860
And then it's left and right.

255
00:10:45,860 --> 00:10:47,120
So it's left is five.

256
00:10:47,120 --> 00:10:48,470
So five gets enqueued.

257
00:10:48,470 --> 00:10:50,270
So we get five over here into our queue.

258
00:10:50,270 --> 00:10:50,780
Right.

259
00:10:50,780 --> 00:10:52,250
And over here it's null.

260
00:10:52,250 --> 00:10:53,660
So we don't have anything over here.

261
00:10:53,660 --> 00:10:56,240
And then count is incremented to one.

262
00:10:56,240 --> 00:10:58,070
One less than one is falsy.

263
00:10:58,070 --> 00:11:01,160
So we come out and this over here is pushed to our output array.

264
00:11:01,160 --> 00:11:05,900
So we get this element which is an array with only three into our output array.

265
00:11:05,900 --> 00:11:08,960
And then finally again we have one element in our queue.

266
00:11:08,960 --> 00:11:15,590
So again we come inside and we're queue length is at this point one right length is one count is changed

267
00:11:15,590 --> 00:11:17,390
to zero when we come over here.

268
00:11:17,390 --> 00:11:19,700
And then car level values is an empty array.

269
00:11:19,700 --> 00:11:25,400
We dequeue when we come we we shift or we dequeue and then we push it to our car level value.

270
00:11:25,400 --> 00:11:28,700
So we get five over here and count is incremented to one.

271
00:11:28,700 --> 00:11:30,200
One less than one is falsy.

272
00:11:30,200 --> 00:11:33,590
So at this point we are going to push this to our output array.

273
00:11:33,590 --> 00:11:35,420
So this is also pushed to our output array.

274
00:11:35,420 --> 00:11:38,060
And this is how our function works.

275
00:11:38,060 --> 00:11:42,230
So this is how we do the level order traversal of the given binary tree.

276
00:11:42,230 --> 00:11:45,980
Now let's take a look at the complexity analysis of this solution.

277
00:11:46,790 --> 00:11:49,160
Now before this let me just clear up some space.

278
00:11:49,160 --> 00:11:51,890
So let's just remove this part over here.

279
00:11:53,910 --> 00:11:56,370
And, uh, let's just remove this also.

280
00:11:59,690 --> 00:12:00,140
All right.

281
00:12:00,140 --> 00:12:02,330
So again over here we had five.

282
00:12:02,930 --> 00:12:05,180
And that that's coming over here in the output array.

283
00:12:05,210 --> 00:12:07,820
Now let's take a look at the time complexity.

284
00:12:07,820 --> 00:12:13,970
The time complexity of this solution is of the order of n, where n is the number of elements in the

285
00:12:13,970 --> 00:12:14,600
binary tree.

286
00:12:14,600 --> 00:12:14,780
Right.

287
00:12:14,780 --> 00:12:15,470
So why is that.

288
00:12:15,470 --> 00:12:16,400
So let's take a look.

289
00:12:16,400 --> 00:12:18,110
What are the things that take up time.

290
00:12:18,110 --> 00:12:19,670
So we have this while loop.

291
00:12:19,670 --> 00:12:21,500
And then we have this while loop over here.

292
00:12:21,530 --> 00:12:26,420
Now this while loop will operate as for once it will loop once for every level.

293
00:12:26,420 --> 00:12:26,720
Right.

294
00:12:26,720 --> 00:12:31,760
So this will be operating doing number of operations equal to the number of levels.

295
00:12:32,890 --> 00:12:36,100
And in this case that's one, two, three, four and five.

296
00:12:36,130 --> 00:12:38,380
Now what about this this while loop over here.

297
00:12:38,380 --> 00:12:43,240
This while loop will loop for a number of times which is equal to n.

298
00:12:43,240 --> 00:12:43,600
Right.

299
00:12:43,600 --> 00:12:44,800
Because why is that so?

300
00:12:44,800 --> 00:12:47,860
Because we have to create this this right.

301
00:12:47,860 --> 00:12:49,900
For we have to create this output array.

302
00:12:49,900 --> 00:12:57,940
And you can see that in each when you add these levels, every element over here 1234567, eight that's

303
00:12:57,940 --> 00:13:01,630
equal to n which is equal to the number of elements in the binary tree.

304
00:13:01,630 --> 00:13:04,000
So that is why it will keep operating for that.

305
00:13:04,000 --> 00:13:04,150
Right.

306
00:13:04,150 --> 00:13:08,950
Because we can see that every element at some point or other will come into our queue.

307
00:13:08,950 --> 00:13:09,190
Right.

308
00:13:09,190 --> 00:13:11,410
It will come into our queue over here.

309
00:13:12,070 --> 00:13:18,280
And then we uh, we are incrementing the count and then we can see this is operating as long as count

310
00:13:18,280 --> 00:13:19,210
is less than length.

311
00:13:19,210 --> 00:13:22,000
So for example, in, in this level, right.

312
00:13:22,000 --> 00:13:27,250
In this level it will happen once because the length is one so zero less than one.

313
00:13:27,250 --> 00:13:28,300
So it will happen once.

314
00:13:28,300 --> 00:13:32,050
So in this level you will have length as two so zero and one.

315
00:13:32,050 --> 00:13:33,550
So this will operate two times.

316
00:13:33,550 --> 00:13:36,580
Similarly over here it will operate for each of these elements.

317
00:13:36,580 --> 00:13:41,020
So you can see that this over here this while loop will operate n number of times.

318
00:13:41,020 --> 00:13:45,460
Now we can see that the time complexity is number of levels plus n.

319
00:13:45,460 --> 00:13:48,280
But then this will be definitely be less than n right.

320
00:13:48,280 --> 00:13:52,570
So that's why we can say that the time complexity of this solution is O of n.

321
00:13:52,870 --> 00:13:55,270
Now what about the space complexity?

322
00:13:55,270 --> 00:14:00,850
For this, let's think about the things that take up space that can scale when the input scales.

323
00:14:00,850 --> 00:14:04,600
So we have our output array and then we have our queue over here.

324
00:14:04,600 --> 00:14:09,580
Now in the output array we can see that we have all elements which are there in the binary tree.

325
00:14:09,580 --> 00:14:15,130
So that's why we can say that the output array takes space of the order of n, where n is the number

326
00:14:15,130 --> 00:14:18,040
of nodes or number of nodes in our binary tree.

327
00:14:18,040 --> 00:14:19,450
Now what about the queue?

328
00:14:19,450 --> 00:14:23,080
Now in the case of a full binary tree, right.

329
00:14:23,080 --> 00:14:24,130
Something like this.

330
00:14:25,000 --> 00:14:26,020
We know that.

331
00:14:27,200 --> 00:14:29,450
The number of leaf nodes, right?

332
00:14:29,450 --> 00:14:33,620
For example, over here you can see you have eight leaf nodes.

333
00:14:33,620 --> 00:14:36,230
So this will be of the order of n by two.

334
00:14:36,230 --> 00:14:36,530
Right.

335
00:14:36,530 --> 00:14:40,970
So I'm saying of the order of n by two because exactly it will be n plus one by two.

336
00:14:40,970 --> 00:14:44,240
But then we can say this will be approximately n by two.

337
00:14:44,270 --> 00:14:47,360
If n is the total number of nodes in the binary tree.

338
00:14:47,360 --> 00:14:47,780
All right.

339
00:14:47,810 --> 00:14:52,550
Now all of these nodes will be there in our queue at the same time.

340
00:14:52,550 --> 00:14:52,940
Right.

341
00:14:52,940 --> 00:14:57,800
So all of these would be put into our queue at the same time when we are processing this level.

342
00:14:57,800 --> 00:14:58,040
Right.

343
00:14:58,040 --> 00:15:01,310
So when we when we dequeue this we will add these two elements.

344
00:15:01,310 --> 00:15:03,620
When we dequeue this one we will add these two.

345
00:15:03,620 --> 00:15:05,120
And these two are still there.

346
00:15:05,120 --> 00:15:07,430
When we dequeue this we will add these two.

347
00:15:07,430 --> 00:15:09,890
And when we dequeue this node we will add these two.

348
00:15:09,890 --> 00:15:10,130
Right.

349
00:15:10,130 --> 00:15:14,300
So all of these nodes are going to be there in our queue at the same time.

350
00:15:14,300 --> 00:15:19,220
So that's why we can say that the queue will take space of the order of n by two.

351
00:15:20,020 --> 00:15:21,670
In the case of a full binary tree.

352
00:15:21,670 --> 00:15:23,200
And then this is just a constant.

353
00:15:23,200 --> 00:15:24,460
So we can just avoid this.

354
00:15:24,460 --> 00:15:26,950
So this also takes space of the order of n.

355
00:15:26,950 --> 00:15:31,720
So again we can say that the space complexity is of the order of n plus n or two n.

356
00:15:31,720 --> 00:15:33,610
But but then two is a constant.

357
00:15:33,610 --> 00:15:37,780
So we can say the space complexity is nothing but O of n.