1
00:00:00,930 --> 00:00:01,620
Hi, everyone.

2
00:00:01,650 --> 00:00:06,520
So in this video, we are going to discuss what is Lawanda traversal of a tree?

3
00:00:06,970 --> 00:00:08,800
OK, let's take an example.

4
00:00:09,420 --> 00:00:11,190
So consider this example.

5
00:00:11,340 --> 00:00:14,520
OK, so law and order means we will traverse level, right?

6
00:00:14,550 --> 00:00:15,720
So this is level one.

7
00:00:16,170 --> 00:00:17,220
Its output is one.

8
00:00:17,490 --> 00:00:18,390
This is level two.

9
00:00:18,630 --> 00:00:20,520
Output of level two is the entry.

10
00:00:21,150 --> 00:00:22,110
This is level three.

11
00:00:22,110 --> 00:00:23,990
So the output is four five.

12
00:00:24,060 --> 00:00:25,550
OK, very, very simple.

13
00:00:25,710 --> 00:00:31,050
We are just traversing level rise, level one, level two and then level three.

14
00:00:31,110 --> 00:00:35,790
OK, so for this tree, this is my level or that level said one, two, three, four, five.

15
00:00:36,480 --> 00:00:40,900
Now let us consider this string and let us try to find out its level or traversal.

16
00:00:40,930 --> 00:00:42,510
OK, so level one.

17
00:00:43,880 --> 00:00:50,210
Now, level to nine and 20, then level three, so this is 15 and seven.

18
00:00:51,590 --> 00:00:55,230
OK, so this is the level of the traversal for this ministry.

19
00:00:55,310 --> 00:00:56,430
OK, very, very simple.

20
00:00:56,450 --> 00:00:59,050
We will just reverse the train level, right?

21
00:00:59,120 --> 00:00:59,470
OK.

22
00:01:00,310 --> 00:01:04,340
Was the tree level right now at this example.

23
00:01:04,400 --> 00:01:07,020
OK, so this is level one seven.

24
00:01:07,280 --> 00:01:09,230
Now this is level two, then in 15.

25
00:01:10,670 --> 00:01:12,240
Now this is my level three.

26
00:01:12,290 --> 00:01:13,980
OK, 15 and 30.

27
00:01:14,600 --> 00:01:16,390
Now this is my level four.

28
00:01:16,550 --> 00:01:17,840
So its output is seven.

29
00:01:17,900 --> 00:01:18,230
OK.

30
00:01:20,140 --> 00:01:25,000
So this is the level where the driver said, look, this is the level driver for this by Nutri.

31
00:01:26,410 --> 00:01:29,690
OK, so I hope you understood what is the meaning of leveland traversal.

32
00:01:29,920 --> 00:01:35,010
Now let's discuss how we can find out the Labrador retriever Saluki, what will be our approach?

33
00:01:36,040 --> 00:01:38,150
So let's first consider an example.

34
00:01:38,210 --> 00:01:38,560
OK.

35
00:01:40,080 --> 00:01:42,180
So I suppose this is a binary tree.

36
00:01:44,950 --> 00:01:51,310
OK, we will try to find out the Leonard traversal for distri, so our approach is very simple to find

37
00:01:51,310 --> 00:01:54,060
out the level of traversal we need UCU.

38
00:01:54,790 --> 00:01:59,230
OK, and now let's see how we can use to find the level traversal.

39
00:01:59,590 --> 00:02:01,750
So the approach is going to be very, very simple.

40
00:02:01,810 --> 00:02:04,840
OK, so what we will do, we will construct a queue.

41
00:02:05,020 --> 00:02:07,210
OK, so let's make a queue.

42
00:02:07,600 --> 00:02:09,250
So initially the queue will be empty.

43
00:02:10,350 --> 00:02:14,940
OK, initially the queue is empty, then what I will do, I will push the root node inside the queue,

44
00:02:15,150 --> 00:02:18,010
OK, so push the root node inside the queue.

45
00:02:18,750 --> 00:02:20,670
Now here I will write my output, OK?

46
00:02:22,370 --> 00:02:26,100
Now, what I will do so I will pop the top element of the gloom.

47
00:02:26,120 --> 00:02:28,640
I will pop different element of the gear and I will print.

48
00:02:28,790 --> 00:02:32,350
So I will print to not after printing, too, I will check.

49
00:02:32,960 --> 00:02:36,370
So the left subtree of to exist, that is three.

50
00:02:36,380 --> 00:02:37,970
So Bush three inside the key.

51
00:02:38,030 --> 00:02:43,580
OK, now Bush three inside the Q similarly check the rates are pretty of to exist.

52
00:02:43,580 --> 00:02:44,800
Yes four exist.

53
00:02:44,810 --> 00:02:46,550
So push for inside the Q.

54
00:02:48,130 --> 00:02:53,250
OK, now, next step again, Bob, a different element of the queue.

55
00:02:53,610 --> 00:02:55,060
OK, so this is three.

56
00:02:55,210 --> 00:02:57,160
After popping, I will print.

57
00:02:57,370 --> 00:02:58,450
So I am printing three.

58
00:02:59,460 --> 00:03:03,350
Now, after printing three, I will check so left off three exist.

59
00:03:03,480 --> 00:03:04,580
Yes, it is five.

60
00:03:04,710 --> 00:03:05,610
So Bush five.

61
00:03:08,380 --> 00:03:11,710
Right off three exists, it is estriol, so I will push Tooele.

62
00:03:13,030 --> 00:03:13,750
Very simple.

63
00:03:13,820 --> 00:03:17,420
OK, now what I will do, I will pop different element.

64
00:03:17,560 --> 00:03:18,430
So this is for.

65
00:03:19,490 --> 00:03:26,420
And Brentford now, after printing for Jack, the left of Ford exist, it does not exist, so do nothing.

66
00:03:27,380 --> 00:03:32,870
Now, check the right of what exists, it exists at this point, so I will push down inside the queue.

67
00:03:34,320 --> 00:03:36,750
OK, so now, Bob, different.

68
00:03:37,120 --> 00:03:37,890
So this is five.

69
00:03:39,100 --> 00:03:46,650
And print five year now after printing five jec so left of five exist, no right of five exists.

70
00:03:46,660 --> 00:03:48,400
It is eight, so push it.

71
00:03:49,770 --> 00:03:52,630
Very simple now, Bob, different elements, so this is.

72
00:03:53,250 --> 00:03:55,050
OK, so I will print will.

73
00:03:56,680 --> 00:04:04,120
Now, check so left off it will exist, no right of tool exists if it exists BUSH So I will push inside

74
00:04:04,120 --> 00:04:04,510
the queue.

75
00:04:05,860 --> 00:04:08,050
Again, I will pop different element.

76
00:04:09,560 --> 00:04:10,910
And I will print it here.

77
00:04:11,280 --> 00:04:12,710
OK, now check for 10.

78
00:04:12,740 --> 00:04:15,460
So this is my pen left off don't exist.

79
00:04:15,470 --> 00:04:17,160
No right of existence.

80
00:04:17,450 --> 00:04:19,850
So do not push anything inside the cube, OK?

81
00:04:20,510 --> 00:04:23,360
Now let's pop it so it will come out.

82
00:04:23,960 --> 00:04:25,000
So this is my ID.

83
00:04:25,310 --> 00:04:28,770
OK, now check left of it exists.

84
00:04:28,940 --> 00:04:29,930
So push nine.

85
00:04:31,320 --> 00:04:34,830
Right off it exist, doesn't it does not exist, so do nothing.

86
00:04:34,890 --> 00:04:37,260
OK, now let's pop this element.

87
00:04:37,320 --> 00:04:38,340
So this is seven.

88
00:04:39,850 --> 00:04:45,900
So right, seven hit now check left of seven exist, no right of seven exertional, so do nothing.

89
00:04:45,910 --> 00:04:47,570
Do not push anything inside the queue.

90
00:04:47,700 --> 00:04:50,020
OK, now pop this element nine.

91
00:04:51,490 --> 00:04:52,570
And printed here.

92
00:04:52,600 --> 00:04:56,900
OK, so left of nine exist, no right of nine exist, no.

93
00:04:57,190 --> 00:04:58,630
So basically do nothing.

94
00:04:58,870 --> 00:05:00,500
Now our queue is empty.

95
00:05:00,550 --> 00:05:02,830
OK, so our queue is empty.

96
00:05:03,100 --> 00:05:05,650
So when our two will become empty, we will stop.

97
00:05:06,780 --> 00:05:08,070
And this is my answer.

98
00:05:09,770 --> 00:05:11,570
This is my level of traversal.

99
00:05:13,960 --> 00:05:21,670
OK, you can see I have two, then three, four, then five to 10, then I have eight and seven and

100
00:05:21,670 --> 00:05:22,540
then I have nine.

101
00:05:22,570 --> 00:05:24,720
OK, so basically our output is correct.

102
00:05:24,730 --> 00:05:25,960
It is hundred percent correct.

103
00:05:25,990 --> 00:05:31,140
OK, so you can see with the help of you, we can easily solved this question.

104
00:05:31,150 --> 00:05:33,540
OK, we can very easily solve this question.

105
00:05:34,150 --> 00:05:37,340
Now let us take one more example to understand it in a better way.

106
00:05:37,410 --> 00:05:40,070
OK, now this time we will take a small example.

107
00:05:40,070 --> 00:05:40,420
Look.

108
00:05:42,140 --> 00:05:44,150
So let's say this is my small example.

109
00:05:46,380 --> 00:05:51,210
OK, so this is a very small example, so initially what we will do, we will construct queue, we will

110
00:05:51,210 --> 00:05:51,990
make a queue.

111
00:05:53,090 --> 00:05:55,040
And our goal will be initially empty.

112
00:05:55,090 --> 00:05:57,470
OK, I would give will be initially empty.

113
00:05:58,640 --> 00:06:00,350
And I will ride my outputted.

114
00:06:01,730 --> 00:06:07,490
So approach is very, very simple to do so initially, I have to put initially I have to push the root

115
00:06:07,490 --> 00:06:07,940
element.

116
00:06:07,940 --> 00:06:09,080
Okay, so I will push to.

117
00:06:10,060 --> 00:06:13,780
Now, let's start so what I will do, I will pop the element.

118
00:06:13,840 --> 00:06:14,140
OK.

119
00:06:14,170 --> 00:06:17,500
So first step is take a different element of the queue.

120
00:06:17,800 --> 00:06:19,230
So this is the first step.

121
00:06:19,570 --> 00:06:20,990
Find out different element.

122
00:06:21,010 --> 00:06:23,370
And this volume outputs right through here.

123
00:06:23,650 --> 00:06:24,270
Now check.

124
00:06:24,910 --> 00:06:27,080
So left off to exist yesterday exist.

125
00:06:27,100 --> 00:06:28,030
So push three.

126
00:06:29,340 --> 00:06:35,030
OK, so second step is, if left exist, then Bush left.

127
00:06:35,040 --> 00:06:38,490
OK, so if left exist, then Bush.

128
00:06:40,980 --> 00:06:44,320
Now for to write also exist, so I will also push forward.

129
00:06:44,400 --> 00:06:48,570
OK, so push for the third step is right exist.

130
00:06:50,810 --> 00:06:53,180
So if right exist, then Bush.

131
00:06:56,000 --> 00:06:58,700
OK, so what I will do after this.

132
00:06:59,710 --> 00:07:02,420
I will pop three, OK, again, different element.

133
00:07:02,500 --> 00:07:06,100
Step one, again, different elements, so I will write three here now.

134
00:07:06,760 --> 00:07:09,310
So left of three exists, five exist.

135
00:07:09,460 --> 00:07:10,420
So push five.

136
00:07:13,120 --> 00:07:17,320
No check for right of pre-exist, no, it doesn't exist, so do nothing.

137
00:07:17,980 --> 00:07:22,880
OK, now, Bob, this element, Bob, different elements of the cessford.

138
00:07:23,260 --> 00:07:25,360
Now check so left of what exist.

139
00:07:25,360 --> 00:07:27,640
No right to exist.

140
00:07:27,670 --> 00:07:28,030
Yes.

141
00:07:28,040 --> 00:07:29,050
So Bush six.

142
00:07:30,660 --> 00:07:34,780
Very simple, then again, a different element printed here.

143
00:07:34,950 --> 00:07:41,020
Now, Jack left of five exist and no right of five exist and also do nothing now pop this element.

144
00:07:41,700 --> 00:07:47,940
So this is six so left of six existing, right of six existing and also do nothing.

145
00:07:47,990 --> 00:07:52,580
OK, and finally, our goal will become empty and we will stop.

146
00:07:52,590 --> 00:07:53,930
And this is my answer.

147
00:07:55,070 --> 00:07:56,270
Two, three, four, five, six.

148
00:07:56,540 --> 00:07:57,990
You can see our answer is right.

149
00:07:58,010 --> 00:08:01,100
Two, three, four, five, six.

150
00:08:01,400 --> 00:08:02,790
OK, so our answer is right.

151
00:08:03,020 --> 00:08:06,200
So these are very three simple steps that we have to perform.

152
00:08:06,230 --> 00:08:06,650
OK.

153
00:08:08,390 --> 00:08:13,130
So what will be our gold, silver, gold is going to look, our gold is going to look very, very simple.

154
00:08:13,780 --> 00:08:16,140
OK, so what will be our gold and what we will do?

155
00:08:16,640 --> 00:08:22,320
So first of all, there will be a loop and it will run while the queue is not empty.

156
00:08:22,370 --> 00:08:24,370
OK, while the queue is not empty.

157
00:08:24,380 --> 00:08:27,770
So what I will do pop different element of the queue.

158
00:08:27,800 --> 00:08:35,470
OK, so basically pop front element of the queue from the front element, then what will do so if left

159
00:08:35,480 --> 00:08:35,980
exist.

160
00:08:36,289 --> 00:08:42,470
So if left exist then push left inside queue, then Bush left inside the queue.

161
00:08:42,710 --> 00:08:51,890
And similarly if the right exist then push right inside the queue, then push right inside the queue.

162
00:08:51,890 --> 00:08:54,020
And this is the complete hold.

163
00:08:54,050 --> 00:08:56,120
OK, so this is the complete gold.

164
00:08:57,040 --> 00:08:59,180
Now, let us modify our question.

165
00:08:59,230 --> 00:09:05,410
OK, so basically suppose now what I was printing initially, so suppose this is the tree.

166
00:09:06,570 --> 00:09:13,560
Now, in which order I am printing, so I am printing like one, then I am printing two three, then

167
00:09:13,560 --> 00:09:15,000
I am printing for five.

168
00:09:16,310 --> 00:09:20,430
OK, so with this logic I can print, I can print like this.

169
00:09:21,390 --> 00:09:28,950
With this logic, I can print like this, but I don't want to print it like this, I want to print it

170
00:09:28,950 --> 00:09:36,780
like this one, then in the next line to comadre, then the next line for Komova if OK, you got me.

171
00:09:37,050 --> 00:09:38,820
I do not want to print like this.

172
00:09:39,780 --> 00:09:42,710
If I want to print like this, then this court will work.

173
00:09:42,900 --> 00:09:47,380
This is a hundred percent correct, but I want to print it like this in the next line.

174
00:09:47,430 --> 00:09:54,720
OK, so first the output of level one, then the output of level to the output of level, then the output

175
00:09:54,720 --> 00:09:56,040
of level four in this way.

176
00:09:56,110 --> 00:09:58,340
OK, so this is the output of level one.

177
00:09:59,070 --> 00:10:02,460
This is the output of level two and this is the output of level three.

178
00:10:02,760 --> 00:10:08,880
OK, so I think you got me how I want to print out and said, OK, now what we will do.

179
00:10:08,880 --> 00:10:15,510
So we will modify the school, we will modify this code and let's see how we will modify the school.

180
00:10:15,600 --> 00:10:17,910
OK, so we will take the help of an.

181
00:10:19,380 --> 00:10:21,720
Now let's see how it will help us.

182
00:10:21,900 --> 00:10:24,930
OK, let's try to find out how it will help us.

183
00:10:26,320 --> 00:10:27,670
So let us take an example.

184
00:10:27,850 --> 00:10:30,790
OK, so suppose this is Maitri.

185
00:10:36,610 --> 00:10:43,210
OK, so what we will do, so let us follow our old approach so our old approaches make UCU.

186
00:10:44,740 --> 00:10:46,480
And initially, our car will be empty.

187
00:10:46,510 --> 00:10:46,840
OK?

188
00:10:48,000 --> 00:10:50,100
So initially, our goal is going to be empty.

189
00:10:51,760 --> 00:10:54,100
OK, so I will ride my outputted.

190
00:10:56,330 --> 00:11:02,960
Now, what we will do so our all approaches Bush, too, so this is the old approach Bush to now the

191
00:11:02,960 --> 00:11:05,270
new approach, says Bush also.

192
00:11:06,700 --> 00:11:09,930
So I will push two things, I will push two things.

193
00:11:09,940 --> 00:11:14,110
First is the basically the root node and second one is basically the null.

194
00:11:14,110 --> 00:11:14,440
Correct.

195
00:11:14,440 --> 00:11:19,040
And I am pushing to think, OK, then we will follow our standard approach.

196
00:11:19,060 --> 00:11:20,680
OK, what is the standard approach?

197
00:11:20,830 --> 00:11:23,620
So Pop, different element right here.

198
00:11:25,210 --> 00:11:28,960
OK, then, after popping the element I will check left exist.

199
00:11:28,990 --> 00:11:32,140
Yes, Bush three, right exist.

200
00:11:32,140 --> 00:11:33,330
Yes, Bush then.

201
00:11:33,880 --> 00:11:35,920
So this is the standard, our old approach.

202
00:11:35,930 --> 00:11:40,990
OK, now Bush, different element, OK, Bush, different elements.

203
00:11:40,990 --> 00:11:42,720
So this time this element personal.

204
00:11:42,790 --> 00:11:44,710
OK, so this is the special case.

205
00:11:45,640 --> 00:11:48,310
This is a special case we are pushing.

206
00:11:48,820 --> 00:11:50,860
OK, so we are getting well.

207
00:11:50,960 --> 00:11:52,720
OK, different analyst Besant.

208
00:11:53,020 --> 00:11:55,630
So when we are popping then so that is a special case.

209
00:11:55,780 --> 00:11:58,120
So I will check after popping out.

210
00:11:58,450 --> 00:11:59,410
Is that empty.

211
00:12:00,010 --> 00:12:01,840
So specialist check.

212
00:12:02,200 --> 00:12:07,960
So after popping, after popping Nele if you is empty.

213
00:12:10,370 --> 00:12:16,100
If go empty, then do nothing, if Grandpre, then do nothing but if.

214
00:12:17,860 --> 00:12:24,610
But if CU is not empty, if not empty, then what we will do, then we will.

215
00:12:24,610 --> 00:12:25,280
Bushnell.

216
00:12:26,820 --> 00:12:28,500
We will push none again.

217
00:12:28,990 --> 00:12:33,560
OK, so in this case, let us know, so is the Green Party.

218
00:12:33,570 --> 00:12:37,840
No, it is containing two elements three and then OK, this containing two elements.

219
00:12:37,860 --> 00:12:39,480
Or if the key is not temporary, I will.

220
00:12:39,480 --> 00:12:41,100
Bushnell So let us Bushnell.

221
00:12:42,150 --> 00:12:43,310
So I will Bushnell.

222
00:12:44,880 --> 00:12:50,440
OK, so now let us pop the next element, so this element is basically three, so.

223
00:12:50,460 --> 00:12:52,270
Right, three in the next lane.

224
00:12:52,920 --> 00:12:59,010
OK, so whenever you are encountering a lull, OK, whenever we face and what we will do, I will write

225
00:12:59,280 --> 00:13:04,140
out, OK, so whenever I am encountering and I will do two things.

226
00:13:04,800 --> 00:13:08,160
First thing, what I will do, I will ride out and line.

227
00:13:10,820 --> 00:13:16,880
Whenever we encounter first Tengiz Singleton line and the second thing is basically we will decide between

228
00:13:16,880 --> 00:13:17,330
these two.

229
00:13:18,770 --> 00:13:26,330
OK, now, after popping out three check, so left exist, yes, right exist, yes, so Bush five and

230
00:13:26,330 --> 00:13:26,630
four.

231
00:13:29,050 --> 00:13:34,610
Again, Bob, then right down here, left exist, no right exist.

232
00:13:34,640 --> 00:13:39,060
Yes, so Bush will Bush to will again be in control.

233
00:13:40,260 --> 00:13:45,330
As soon as we encounter what we will do, our first step is basically leveland so I will go ahead.

234
00:13:46,340 --> 00:13:51,740
Now, a second step is if goo is not empty, then Bushnell again, so I will push again.

235
00:13:52,790 --> 00:13:53,990
So I have none again.

236
00:13:54,370 --> 00:13:54,770
OK.

237
00:13:56,450 --> 00:14:02,840
Now, different elements of this is five, so right, five here, not left exist, yes, right exist.

238
00:14:02,840 --> 00:14:04,040
And so Bush 15.

239
00:14:05,810 --> 00:14:07,310
Then pop the front element.

240
00:14:07,340 --> 00:14:12,440
This is for the right for here now, now check left exist, no right exist and also do nothing.

241
00:14:12,830 --> 00:14:14,690
OK, now I have to.

242
00:14:15,330 --> 00:14:20,510
OK, so basically right now a chick left existence right exists.

243
00:14:20,510 --> 00:14:22,250
So Bush 13 and 17.

244
00:14:22,910 --> 00:14:24,710
So Bush 13 and 17.

245
00:14:28,060 --> 00:14:34,870
Now, again, we are in control, so as soon as you can control, I will go to next lane and then check

246
00:14:34,870 --> 00:14:36,360
if the queue is not empty.

247
00:14:36,370 --> 00:14:39,640
Bushnell again, so queue is not empty, I will push again.

248
00:14:40,900 --> 00:14:42,720
OK, so now what?

249
00:14:43,090 --> 00:14:46,940
Fifteen and right, fifteen here now, Jack, left, no right exist.

250
00:14:46,980 --> 00:14:47,260
Yes.

251
00:14:47,260 --> 00:14:48,130
So Bush 18.

252
00:14:49,120 --> 00:14:50,320
So push it in.

253
00:14:52,480 --> 00:14:54,950
Now, check now 13.

254
00:14:54,970 --> 00:14:59,470
OK, so right, 13 here left exist, no right exist, no do nothing.

255
00:14:59,740 --> 00:15:01,450
Now, pop 17 right.

256
00:15:01,450 --> 00:15:03,190
17 here left exist.

257
00:15:03,190 --> 00:15:04,060
No right exist.

258
00:15:04,060 --> 00:15:04,930
No do nothing.

259
00:15:05,230 --> 00:15:06,150
No pop none.

260
00:15:07,000 --> 00:15:09,400
OK, so after popping out what do do.

261
00:15:09,430 --> 00:15:10,600
I will go to next lane.

262
00:15:10,600 --> 00:15:11,680
This is the first to step.

263
00:15:12,500 --> 00:15:18,490
First step is basically go to the next lane and now check if goo is not empty push again.

264
00:15:18,490 --> 00:15:19,780
So I will push monologuing.

265
00:15:23,450 --> 00:15:29,570
Now, Bob, differently when this is 18, so right, 18 here left exist, no right exist, no.

266
00:15:30,140 --> 00:15:32,270
Then do nothing then Bob differently.

267
00:15:32,460 --> 00:15:38,020
So this isn't as soon as going to go to the next step and then check.

268
00:15:38,210 --> 00:15:40,340
So in this case goes empty.

269
00:15:41,050 --> 00:15:42,890
If you is empty, do nothing.

270
00:15:43,160 --> 00:15:43,970
Do nothing.

271
00:15:44,330 --> 00:15:45,860
OK, and finally, what will happen.

272
00:15:45,860 --> 00:15:49,070
Our school becomes empty now our queue is empty.

273
00:15:49,670 --> 00:15:52,130
So when the queue will become empty, we are done.

274
00:15:52,130 --> 00:15:52,820
We will stop.

275
00:15:52,820 --> 00:15:54,020
And this is my answer.

276
00:15:55,170 --> 00:15:57,360
This is my answer, which is 100 percent correct.

277
00:15:57,430 --> 00:15:59,770
OK, we are operating level, right?

278
00:15:59,820 --> 00:16:01,460
So this is output of level one.

279
00:16:01,470 --> 00:16:05,220
This is output of level two, output, level three, four and five.

280
00:16:06,330 --> 00:16:07,810
OK, so what is that?

281
00:16:07,830 --> 00:16:10,010
What is like Vivyan Lucindale.

282
00:16:10,440 --> 00:16:17,670
So signal is used to differentiate between levels nahles used to differentiate between levels.

283
00:16:18,010 --> 00:16:25,590
OK, so basically as soon as you can control, as soon as you encounter, that means one level has finished.

284
00:16:25,650 --> 00:16:32,550
OK, so as soon as we encounter Annell, that means the current level has finished.

285
00:16:32,880 --> 00:16:34,350
Current level has finished.

286
00:16:34,680 --> 00:16:35,940
OK, very, very simple.

287
00:16:37,230 --> 00:16:39,810
So how we can modify this so-called.

288
00:16:43,360 --> 00:16:48,600
So what we will do so we will modified this code here, we will write a special condition, what will

289
00:16:48,610 --> 00:16:49,460
a special condition.

290
00:16:49,810 --> 00:16:53,110
So basically when I am popping different element, I will check.

291
00:16:53,500 --> 00:16:55,330
So if different element.

292
00:16:56,330 --> 00:17:03,180
It's basically a null character, then our first step is to basically print and then basically go to

293
00:17:03,180 --> 00:17:03,710
the next line.

294
00:17:03,890 --> 00:17:08,780
And the second step is basically I will decide whether I have to Bushnell or do not.

295
00:17:08,780 --> 00:17:11,609
Bushnell OK, if the kill.

296
00:17:11,780 --> 00:17:14,270
So basically, if the queue is not empty, then I will.

297
00:17:14,270 --> 00:17:16,310
Bushnell If that is temporary then do not.

298
00:17:16,310 --> 00:17:16,780
Bushnell.

299
00:17:17,910 --> 00:17:18,839
Very, very simple.

300
00:17:19,500 --> 00:17:27,240
OK, so vinyl used so nahles used to basically it is used to differentiate between the levels.

301
00:17:28,730 --> 00:17:33,150
So as soon as you will encounter a character that means the current level has finished.

302
00:17:33,170 --> 00:17:38,270
If the current level has finished to basically go to the next level, go to the next level.

303
00:17:38,840 --> 00:17:40,310
OK, very simple.

304
00:17:42,010 --> 00:17:46,930
Now, let us take one more example to help you understand it better, OK, this time we will take a

305
00:17:46,930 --> 00:17:47,720
small example.

306
00:17:47,740 --> 00:17:49,490
So two, three, 10 and 12.

307
00:17:49,630 --> 00:17:51,010
OK, so this is Mitry.

308
00:17:51,010 --> 00:17:54,040
So what I will do, I will make UCU initially.

309
00:17:54,040 --> 00:17:55,480
I will will be empty now.

310
00:17:55,480 --> 00:17:56,770
I will push two things.

311
00:17:56,770 --> 00:17:57,940
I will push route.

312
00:17:58,690 --> 00:18:00,610
I will push a null corrector.

313
00:18:01,950 --> 00:18:02,650
Very simple.

314
00:18:03,120 --> 00:18:11,040
Now, I will write my output here, so, Bob, different elements, the system now left exist.

315
00:18:11,070 --> 00:18:12,360
Yes, right exist.

316
00:18:12,390 --> 00:18:12,720
Yes.

317
00:18:12,720 --> 00:18:15,750
So push three and then push three and then.

318
00:18:17,590 --> 00:18:24,000
OK, now, Bob, the next element, so this isn't all, so as soon as control the current level is finished,

319
00:18:24,030 --> 00:18:25,480
go to the next level.

320
00:18:26,000 --> 00:18:28,900
And if the queue is not empty, Bush again.

321
00:18:29,650 --> 00:18:30,870
So it is not pretty.

322
00:18:30,880 --> 00:18:32,020
I am pushing their luck in.

323
00:18:33,130 --> 00:18:39,760
Now, Bob, different elements of the story, so right here left exist, no right exist, no do nothing

324
00:18:40,410 --> 00:18:41,730
but a different element.

325
00:18:42,040 --> 00:18:44,950
So this cistern left exist.

326
00:18:45,070 --> 00:18:47,230
No right exists.

327
00:18:47,230 --> 00:18:52,150
So Bush will Bush will now be optional.

328
00:18:52,510 --> 00:18:58,330
So as soon as he can control the current level is finished and go to the next level, do is not empty.

329
00:18:58,330 --> 00:18:59,500
So Bush again.

330
00:19:00,810 --> 00:19:02,580
We will push again.

331
00:19:03,060 --> 00:19:09,180
OK, now, Popplewell, right, well, here, left existant, all right, existential.

332
00:19:10,300 --> 00:19:16,510
Now, pop, again, go to the next level now, this time the queue is empty, if it goes empty, do

333
00:19:16,510 --> 00:19:17,590
not push again.

334
00:19:17,620 --> 00:19:22,170
So finally our queue is empty and we will stop.

335
00:19:22,180 --> 00:19:23,280
And this is my answer.

336
00:19:25,940 --> 00:19:29,180
So this is level one, this is level two, and this is level three.

337
00:19:29,730 --> 00:19:33,730
OK, so our output is right now, it seems to have understood the logic.

338
00:19:33,740 --> 00:19:35,810
I think now is the time to write the code.

339
00:19:35,880 --> 00:19:37,820
OK, so let's write the code.

340
00:19:41,650 --> 00:19:47,460
OK, so this is the question that I was in, so in this question, we do not have to print anything.

341
00:19:47,470 --> 00:19:48,680
Basically I have to return.

342
00:19:48,760 --> 00:19:50,450
OK, how we can return.

343
00:19:50,800 --> 00:19:55,590
So basically, you can see the return type of the function is basically the private property.

344
00:19:55,620 --> 00:19:57,230
Just so basically these are truly free.

345
00:19:57,250 --> 00:19:59,020
So you can see the output.

346
00:19:59,050 --> 00:19:59,850
This is level one.

347
00:19:59,860 --> 00:20:02,260
So I am printing three here now, level two.

348
00:20:02,530 --> 00:20:04,990
So this is level two and this is level three.

349
00:20:04,990 --> 00:20:06,010
So this is level three.

350
00:20:06,050 --> 00:20:08,020
OK, so that part of the property.

351
00:20:08,130 --> 00:20:10,000
So this is a vector of integers.

352
00:20:13,060 --> 00:20:18,370
This is also a matter of intelligence and this is a vector of intelligence, and finally I have a bigger

353
00:20:18,370 --> 00:20:18,620
one.

354
00:20:18,640 --> 00:20:21,710
Basically, it is a tool that I have to return to the area.

355
00:20:21,800 --> 00:20:22,150
OK.

356
00:20:24,100 --> 00:20:26,200
And input is basically the three.

357
00:20:26,770 --> 00:20:28,900
OK, so now let's write the good.

358
00:20:32,610 --> 00:20:38,820
So first, let us create our answer, OK, so our answer is basically a Tooryalai.

359
00:20:44,210 --> 00:20:46,830
So vector of vector of integers, let's name it.

360
00:20:47,270 --> 00:20:48,980
OK, we will be my answer.

361
00:20:49,080 --> 00:20:50,270
Initially it is empty.

362
00:20:53,040 --> 00:20:54,210
And now let us create.

363
00:20:55,910 --> 00:21:01,200
I've had third temp, OK, because to push anything inside this vector, I have to push a vector.

364
00:21:01,250 --> 00:21:03,580
OK, so I will push this temp vector.

365
00:21:03,830 --> 00:21:05,870
So this is initially empty.

366
00:21:05,940 --> 00:21:09,560
OK, now what we have to do, I have to make a queue.

367
00:21:09,680 --> 00:21:10,900
OK, step one.

368
00:21:11,270 --> 00:21:13,850
So let us right the step and then we will follow the steps.

369
00:21:14,810 --> 00:21:16,360
So the steps are very simple.

370
00:21:16,670 --> 00:21:19,010
So step one is basically make UCU.

371
00:21:20,800 --> 00:21:24,820
McHugh and Bush do things, so I will push two things.

372
00:21:24,860 --> 00:21:30,380
So first thing is basically I will push a node and second thing is basically I will push the null character.

373
00:21:30,820 --> 00:21:34,060
OK, second step is basically I have to use a loop.

374
00:21:34,340 --> 00:21:37,410
So while the queue is not empty, I have to bend.

375
00:21:38,020 --> 00:21:39,700
So I do not have to print in this question.

376
00:21:39,700 --> 00:21:41,500
I have to store and then I have to return.

377
00:21:41,560 --> 00:21:44,440
OK, so what will do, get the top element.

378
00:21:44,990 --> 00:21:48,580
OK, so get a friend element of the queue.

379
00:21:48,760 --> 00:21:50,290
Get different element of the queue.

380
00:21:50,530 --> 00:21:52,320
Now here I have two conditions.

381
00:21:52,840 --> 00:21:54,760
So if the front element is null.

382
00:21:56,540 --> 00:22:00,970
The front element can be different elements, well, that means the current level has been finished,

383
00:22:01,250 --> 00:22:02,710
so I have to do two things.

384
00:22:02,720 --> 00:22:05,340
So first, things basically go to the next level.

385
00:22:05,370 --> 00:22:06,860
So I will look out and learn.

386
00:22:08,210 --> 00:22:14,160
And after doing this, I have two options, which again, do not Bushnell again.

387
00:22:14,210 --> 00:22:15,680
OK, so do not.

388
00:22:15,680 --> 00:22:16,340
Bushnell.

389
00:22:16,490 --> 00:22:17,320
Bushnell We will.

390
00:22:17,330 --> 00:22:24,350
Bushnell if the queue is not empty, if you not and then Bushnell otherwise do not Bushnell.

391
00:22:25,510 --> 00:22:29,810
OK, so if the front element is not null, then what will do?

392
00:22:29,980 --> 00:22:35,890
So I will print, I will print and now I will check, so I will check.

393
00:22:35,890 --> 00:22:44,020
If left exist, then push left inside the queue and if right to exist, then push right inside the queue.

394
00:22:44,310 --> 00:22:47,020
OK, so I will follow these steps.

395
00:22:47,020 --> 00:22:48,610
I will follow these steps.

396
00:22:48,850 --> 00:22:52,600
Now let us first let us create given Bush two things, OK.

397
00:22:53,880 --> 00:23:02,770
So CU is basically built in big data subject and C++, OK, so I have to create a queue of three a.m.

398
00:23:02,880 --> 00:23:04,890
OK, not often tedious.

399
00:23:04,890 --> 00:23:09,240
I have to create new freenode style so that I can access the left and the right subtree.

400
00:23:09,330 --> 00:23:11,730
OK, it will not be often tedious.

401
00:23:12,010 --> 00:23:17,060
It will be of order because I have to access it left and right subtree.

402
00:23:17,160 --> 00:23:17,490
OK.

403
00:23:18,660 --> 00:23:20,070
So let's Namadgi only.

404
00:23:21,680 --> 00:23:25,460
Then good old Bush, I have to push two things first one is the.

405
00:23:26,870 --> 00:23:28,330
Second one is Denel character.

406
00:23:28,370 --> 00:23:30,080
OK, now this special character.

407
00:23:31,100 --> 00:23:33,260
That will help us differentiate between levels.

408
00:23:34,630 --> 00:23:39,370
Now, again, what we have to do so while is not empty, got a different element.

409
00:23:41,460 --> 00:23:43,980
So while she not empty.

410
00:23:46,870 --> 00:23:52,480
What I have to do is get different element, OK, and friend element is basically adrenalized start.

411
00:23:53,530 --> 00:23:53,980
So.

412
00:23:55,180 --> 00:23:57,400
Dean, Alstyle, let's call it friend.

413
00:23:57,700 --> 00:24:01,060
OK, so Dean or storefront is basically good old friend.

414
00:24:03,440 --> 00:24:09,410
So I have the front element now I have to check, so I have to use this condition, I have to compare

415
00:24:09,500 --> 00:24:12,980
different elements within a different element or not.

416
00:24:13,010 --> 00:24:14,780
OK, so let's check.

417
00:24:15,290 --> 00:24:17,500
So if a friend element is null.

418
00:24:19,560 --> 00:24:20,520
I have to do something.

419
00:24:21,700 --> 00:24:24,340
In the last part, I have to do something else.

420
00:24:24,490 --> 00:24:32,380
OK, so now first let's write the l'esprit, OK, first let us write this part so I do not have to print

421
00:24:32,380 --> 00:24:32,800
anything.

422
00:24:32,980 --> 00:24:37,780
I have to basically store it, OK, I have to store it now.

423
00:24:37,780 --> 00:24:41,470
Let's do it and I will check if left and right exist then push.

424
00:24:41,840 --> 00:24:42,220
OK.

425
00:24:44,880 --> 00:24:48,380
So basically, what is the data, so data is not value.

426
00:24:48,460 --> 00:24:53,430
OK, so I was told it and temp Fambul Sturdee current level.

427
00:24:53,970 --> 00:24:56,280
So Temperton push back.

428
00:24:58,410 --> 00:25:02,490
What is the value, so value is basically f d'arte value.

429
00:25:03,680 --> 00:25:04,030
OK.

430
00:25:05,420 --> 00:25:06,590
So the FLW.

431
00:25:08,360 --> 00:25:11,540
So if it's different element, I am pushing its value.

432
00:25:12,020 --> 00:25:14,060
OK, now I have to check.

433
00:25:14,980 --> 00:25:16,660
So if the left exist.

434
00:25:19,010 --> 00:25:22,820
Then I have to push it inside the so called out push left.

435
00:25:26,170 --> 00:25:27,400
Similarly, I will check.

436
00:25:27,430 --> 00:25:29,410
So if right to exist.

437
00:25:33,900 --> 00:25:35,640
Then I will push the right.

438
00:25:44,850 --> 00:25:46,630
OK, very, very simple.

439
00:25:46,860 --> 00:25:48,530
Now, let us do this part.

440
00:25:48,630 --> 00:25:53,640
OK, so in this part, our first step was to basically do so out and line.

441
00:25:53,850 --> 00:25:55,690
But here we do not have to print anything.

442
00:25:55,890 --> 00:25:58,380
So instead of printing a new line, what we will do?

443
00:25:59,300 --> 00:26:00,630
I will push my answer.

444
00:26:00,680 --> 00:26:02,630
OK, so this is our answer.

445
00:26:03,410 --> 00:26:04,190
What is temp?

446
00:26:04,400 --> 00:26:07,280
So temp is basically storing the result of current level.

447
00:26:07,310 --> 00:26:12,620
OK, temp is storing the result of current level.

448
00:26:15,010 --> 00:26:18,760
Now, at this point, the current level has been finished, if I may, and counting.

449
00:26:18,840 --> 00:26:21,100
Well, that means the current level has been finished.

450
00:26:21,370 --> 00:26:24,850
So what I will do vs my answer so we don't.

451
00:26:26,090 --> 00:26:31,580
Push back, so I have to push a vector and temp is that vector means temporary.

452
00:26:32,120 --> 00:26:36,300
OK, so after pushing the temp, what I will do, I will make the temp empty.

453
00:26:36,350 --> 00:26:39,470
OK, so I think that clearly is a function.

454
00:26:40,880 --> 00:26:47,640
Our team members now empty, it does not contain a single element, it is containing zero elements.

455
00:26:47,660 --> 00:26:48,560
What I'm not clear.

456
00:26:49,560 --> 00:26:50,490
Now, I would have to do.

457
00:26:51,630 --> 00:26:56,850
So you can see yourself, I have to see out and then I will check if the queue is not empty.

458
00:26:56,850 --> 00:26:57,660
Bushnell again.

459
00:26:59,710 --> 00:27:01,150
OK, so very simple condition.

460
00:27:02,160 --> 00:27:02,910
So if.

461
00:27:03,730 --> 00:27:05,410
The queue is not empty.

462
00:27:06,720 --> 00:27:08,200
Then I have to push again.

463
00:27:08,460 --> 00:27:09,780
OK, so not.

464
00:27:11,630 --> 00:27:12,260
Bushnell.

465
00:27:14,990 --> 00:27:16,130
OK, so I think.

466
00:27:17,680 --> 00:27:19,360
After this line, basically, while.

467
00:27:20,440 --> 00:27:25,990
The queue is becomes empty out until it's ready, and my answer is to be so let's sit in our court and

468
00:27:25,990 --> 00:27:27,580
then we will try to submit our good.

469
00:27:34,310 --> 00:27:36,530
OK, so what is the edit spelling mistake?

470
00:27:49,760 --> 00:27:51,560
OK, so we are getting time limited exit.

471
00:27:51,660 --> 00:27:55,580
That means there is some infinite loop, this is not becoming empty.

472
00:27:55,760 --> 00:27:56,130
OK.

473
00:27:56,680 --> 00:28:00,420
OK, so what we are doing so after getting a different element.

474
00:28:00,470 --> 00:28:01,160
So first thing.

475
00:28:02,360 --> 00:28:10,630
We are getting excited, so this is very simple, so we are getting excited because we are popping different

476
00:28:10,630 --> 00:28:13,310
element and we we are getting different elements.

477
00:28:13,310 --> 00:28:15,460
So this is to get a different element.

478
00:28:15,820 --> 00:28:18,870
I have to also pop different elements, so I have to write good pop.

479
00:28:19,150 --> 00:28:21,580
So basically, you will never become empty, OK?

480
00:28:22,180 --> 00:28:25,660
You will never become empty and it will become infinite loop.

481
00:28:25,690 --> 00:28:30,570
OK, so that's why because of the infinite loop, I am getting timely and excited.

482
00:28:30,820 --> 00:28:33,910
So after getting different element, I have to also pop that element.

483
00:28:33,920 --> 00:28:34,810
You can see yourself.

484
00:28:36,130 --> 00:28:41,980
So basically, after getting a different element, I also have to pop their element, OK, and if I

485
00:28:41,980 --> 00:28:44,200
got to pop here now, let's pop the element.

486
00:28:46,060 --> 00:28:50,860
So could our friend then, good artpop, we also have to remove the element.

487
00:28:50,950 --> 00:28:51,180
OK.

488
00:28:58,250 --> 00:29:00,080
OK, so now let's meet our good.

489
00:29:05,690 --> 00:29:13,550
OK, so if basically the tape does not exist, we do not handle that case, OK, so let's handle that

490
00:29:13,550 --> 00:29:13,880
case.

491
00:29:13,910 --> 00:29:15,120
So if the route isn't.

492
00:29:18,320 --> 00:29:19,640
So if rotational.

493
00:29:22,750 --> 00:29:23,900
Then what William Allen said.

494
00:29:23,930 --> 00:29:26,410
So basically my answer will be empty.

495
00:29:26,440 --> 00:29:29,070
OK, so return V V is empty at this point, OK?

496
00:29:29,610 --> 00:29:31,030
V is not containing anything.

497
00:29:31,030 --> 00:29:32,050
So I will return my.

498
00:29:38,780 --> 00:29:40,820
OK, so our goal is 100 percent correct.

499
00:29:40,850 --> 00:29:42,020
Our goal is working fine.

500
00:29:42,270 --> 00:29:42,650
OK.

501
00:29:43,780 --> 00:29:47,740
Now, let us discuss the time and the space complexity of our resolution.

502
00:29:49,750 --> 00:29:55,780
So what is the time, complexity, so time, complexity is very simple, it is big often where and is

503
00:29:55,780 --> 00:29:57,580
the number of nodes in the binary.

504
00:29:57,790 --> 00:30:04,480
OK, we are just going through each and every node and we are outputting that node via printing that

505
00:30:04,480 --> 00:30:04,810
node.

506
00:30:04,840 --> 00:30:09,870
OK, so NQ basically every operation, this operation is basically Konstantine.

507
00:30:10,720 --> 00:30:12,390
This operation is also constrained.

508
00:30:12,670 --> 00:30:15,780
OK, so Bush operation is also constrained.

509
00:30:16,060 --> 00:30:19,190
So NQ everything is Konstantine.

510
00:30:19,210 --> 00:30:22,390
So basically our time complexities big off and only.

511
00:30:22,750 --> 00:30:25,060
OK, and what is our space complexity.

512
00:30:25,270 --> 00:30:28,480
So what we are doing, we are using accum we are creating a AQ.

513
00:30:28,810 --> 00:30:31,960
So in the worst case our space complexity will be big often.

514
00:30:32,240 --> 00:30:32,650
OK.

515
00:30:34,020 --> 00:30:37,530
So this is the time and the space complexity, more time, big of an.

516
00:30:39,760 --> 00:30:43,210
So these are the time and the space complexity for the level of the traversal.

517
00:30:43,480 --> 00:30:48,610
OK, so if you have any doubt in the code or in the logic, you can ask me, OK, thank you.