1
00:00:00,650 --> 00:00:01,700
Welcome back.

2
00:00:01,700 --> 00:00:08,510
Now to solve this question, let's see how we can make slight modifications to the algorithm of the

3
00:00:08,510 --> 00:00:10,970
level order traversal to get our answer.

4
00:00:10,970 --> 00:00:14,270
So first over here let's try to think about right side view.

5
00:00:14,270 --> 00:00:14,660
All right.

6
00:00:14,660 --> 00:00:16,340
So you're looking from the right.

7
00:00:16,340 --> 00:00:19,610
So you should be getting 7183 and five.

8
00:00:19,610 --> 00:00:21,710
And this is the algorithm which we discussed.

9
00:00:21,710 --> 00:00:26,570
Or the pseudocode which we discussed when we had the video on level order traversal.

10
00:00:26,570 --> 00:00:26,990
All right.

11
00:00:26,990 --> 00:00:30,950
So over here what we want is again let me let's just quickly recap.

12
00:00:30,950 --> 00:00:32,480
We start at the root node.

13
00:00:32,480 --> 00:00:34,520
Now we're going to insert it to our queue.

14
00:00:34,520 --> 00:00:35,030
All right.

15
00:00:35,030 --> 00:00:39,230
And then we will find the length of the queue which is equal to one at this point.

16
00:00:39,230 --> 00:00:41,570
And then the count is initialized to zero.

17
00:00:41,570 --> 00:00:43,310
And then there is something in the queue.

18
00:00:43,310 --> 00:00:45,200
So we come inside this while loop.

19
00:00:45,200 --> 00:00:51,020
Now there in level order traversal, we needed an array to have all the elements in that particular

20
00:00:51,020 --> 00:00:51,590
level, right.

21
00:00:51,590 --> 00:00:54,260
So that's why we had car level which was an empty array.

22
00:00:54,260 --> 00:00:55,700
But over here we don't need this.

23
00:00:55,700 --> 00:00:57,710
So I'm just removing this now.

24
00:00:57,710 --> 00:00:59,450
We still need this over here.

25
00:00:59,450 --> 00:00:59,660
Right.

26
00:00:59,660 --> 00:01:03,860
For again in this part we said count is equal to zero and we find the length.

27
00:01:04,430 --> 00:01:06,650
So we have found the length is equal to one.

28
00:01:06,650 --> 00:01:11,630
Now we have this while loop which will operate while count is less than length.

29
00:01:11,630 --> 00:01:17,450
Now inside this while loop we dequeue so that the the process is the same we dequeue.

30
00:01:17,450 --> 00:01:20,690
Then over here we have this step where we push to current level.

31
00:01:20,690 --> 00:01:22,100
So we don't need this over here.

32
00:01:22,100 --> 00:01:22,490
Right.

33
00:01:22,490 --> 00:01:26,690
So we don't need this because we are not discussing level order traversal.

34
00:01:26,690 --> 00:01:28,970
We are going to enqueue the left and right.

35
00:01:29,360 --> 00:01:31,340
And then we will increment count.

36
00:01:31,340 --> 00:01:33,080
So this is going to be the same.

37
00:01:33,080 --> 00:01:40,310
Now after we increment the count we can check whether we are at the right most element of the particular

38
00:01:40,310 --> 00:01:40,760
level.

39
00:01:40,760 --> 00:01:42,080
So how can we check that.

40
00:01:42,080 --> 00:01:42,440
Right.

41
00:01:42,440 --> 00:01:45,710
For example, if let's say over here, we are over here.

42
00:01:45,710 --> 00:01:45,890
Right.

43
00:01:45,890 --> 00:01:47,600
So initially count is equal to zero.

44
00:01:47,600 --> 00:01:49,130
Now length is one.

45
00:01:49,130 --> 00:01:53,240
Now when count is equal to zero we come inside and we increment count.

46
00:01:53,240 --> 00:01:54,500
So count becomes one.

47
00:01:54,500 --> 00:01:57,350
So when count is equal to length right.

48
00:01:57,470 --> 00:02:03,140
Then if if we make that check over here then we can be sure that we are at the right most element in

49
00:02:03,140 --> 00:02:04,610
that particular level.

50
00:02:04,610 --> 00:02:04,880
Right.

51
00:02:04,880 --> 00:02:09,590
So if count is equal to length we just need to push it to our right array.

52
00:02:09,590 --> 00:02:11,750
So let's call this array right view.

53
00:02:11,750 --> 00:02:12,140
All right.

54
00:02:12,140 --> 00:02:18,350
So we just need to push it the element to our right view array if the count is equal to the length.

55
00:02:18,350 --> 00:02:24,110
So in this case we push seven because the count is equal to length because after we increment count.

56
00:02:24,110 --> 00:02:24,380
All right.

57
00:02:24,380 --> 00:02:29,540
So after we increment count inside this itself we can check or we can write it outside also.

58
00:02:29,540 --> 00:02:31,190
So I'm just going to check it inside.

59
00:02:31,190 --> 00:02:33,080
So if count after incrementing.

60
00:02:33,080 --> 00:02:33,290
All right.

61
00:02:33,290 --> 00:02:34,670
So it's going to be somewhere over here.

62
00:02:34,670 --> 00:02:38,750
If count is equal to the length then we are just going to push it to our array over here.

63
00:02:38,750 --> 00:02:40,550
So in this case we push seven.

64
00:02:40,550 --> 00:02:44,870
Now we proceed again we have enqueued our left and right over here.

65
00:02:44,870 --> 00:02:47,750
So 11 and one are going to be in our queue.

66
00:02:47,750 --> 00:02:50,360
And again this this thing over here is not required.

67
00:02:50,360 --> 00:02:52,250
Again we are not dealing with level right.

68
00:02:52,250 --> 00:02:56,840
So I'm just taking this over here so that you can work upon something which you have already seen so

69
00:02:56,840 --> 00:02:58,670
that you can build upon the knowledge.

70
00:02:58,670 --> 00:02:58,970
Right.

71
00:02:58,970 --> 00:03:01,940
So again, we come over here, we see that there are things in our queue.

72
00:03:01,940 --> 00:03:03,200
So we come inside.

73
00:03:03,200 --> 00:03:04,400
Count is equal to zero.

74
00:03:04,400 --> 00:03:06,740
And length at this point is made to two.

75
00:03:06,740 --> 00:03:08,960
Because we have two elements in our queue.

76
00:03:08,960 --> 00:03:12,170
Now we come inside and zero is less than two.

77
00:03:12,200 --> 00:03:18,710
So we come inside VDC and we are going to enqueue its children, which is just seven, and we will increment

78
00:03:18,710 --> 00:03:19,100
count.

79
00:03:19,100 --> 00:03:21,140
So count is equal to one at this point.

80
00:03:21,140 --> 00:03:22,880
And again these two are not equal.

81
00:03:22,880 --> 00:03:25,520
So again we come over here we dequeue.

82
00:03:25,520 --> 00:03:29,540
So we take one out and we enqueue its children which is two and eight.

83
00:03:30,480 --> 00:03:32,220
Again, we increment count.

84
00:03:32,220 --> 00:03:34,560
So count becomes equal to two at this point.

85
00:03:34,590 --> 00:03:36,300
Now count is equal to length.

86
00:03:36,300 --> 00:03:41,670
So this particular element right which we just now took out which is one is going to be pushed into

87
00:03:41,670 --> 00:03:42,570
our right view.

88
00:03:42,570 --> 00:03:45,600
So we get one over here and then we proceed.

89
00:03:45,600 --> 00:03:48,330
We see that again there are things in the queue.

90
00:03:48,330 --> 00:03:48,690
All right.

91
00:03:48,690 --> 00:03:51,030
So we again change count to zero.

92
00:03:51,030 --> 00:03:53,040
And length now is equal to three.

93
00:03:53,040 --> 00:03:54,420
So length is equal to three.

94
00:03:54,420 --> 00:03:57,420
Again we come inside zero is less than three.

95
00:03:57,420 --> 00:04:01,290
So we dequeue and we are going to enqueue its children.

96
00:04:01,290 --> 00:04:02,520
So there are no children.

97
00:04:02,520 --> 00:04:04,140
And then we will increment count.

98
00:04:04,140 --> 00:04:05,370
So count is equal to one.

99
00:04:05,370 --> 00:04:07,380
Again we'd Q all right.

100
00:04:07,380 --> 00:04:10,290
And we're going to enqueue its children which is three.

101
00:04:10,290 --> 00:04:11,700
So we add three over here.

102
00:04:11,700 --> 00:04:14,430
And count now is equal to is incremented.

103
00:04:14,430 --> 00:04:15,540
So count becomes two.

104
00:04:15,570 --> 00:04:17,190
Two is also not equal to length.

105
00:04:17,190 --> 00:04:20,100
So again we come over here and we dequeue right.

106
00:04:20,100 --> 00:04:21,600
So we dequeue we take this eight.

107
00:04:21,600 --> 00:04:23,070
Now count becomes three.

108
00:04:23,070 --> 00:04:26,190
When we again it does not have any children to enqueue.

109
00:04:26,190 --> 00:04:27,630
And then we increment count.

110
00:04:27,630 --> 00:04:29,070
So now count is equal.

111
00:04:29,070 --> 00:04:34,860
So because count is equal to the length we will just push that particular value which is eight to our

112
00:04:34,860 --> 00:04:35,400
output array.

113
00:04:35,400 --> 00:04:38,550
So you can see we are getting 718 right.

114
00:04:38,550 --> 00:04:42,900
Similarly we continue again we see that there is one element in our queue.

115
00:04:42,900 --> 00:04:43,980
So we come inside.

116
00:04:43,980 --> 00:04:45,540
Count is again changed to zero.

117
00:04:45,540 --> 00:04:46,890
So let's just clear this up.

118
00:04:46,890 --> 00:04:49,020
So count is again changed to zero.

119
00:04:50,150 --> 00:04:52,100
And length now is equal to one.

120
00:04:52,100 --> 00:04:55,670
So we come inside VDC this and it has children.

121
00:04:55,670 --> 00:04:56,240
It has five.

122
00:04:56,240 --> 00:04:58,880
So we enqueue the child and then we increment count.

123
00:04:58,880 --> 00:04:59,450
So one.

124
00:04:59,450 --> 00:05:00,950
Now count is equal to length.

125
00:05:00,950 --> 00:05:06,680
So this element, the element which we just now dequeued is going to be added to our right view array.

126
00:05:06,680 --> 00:05:07,940
So we get three also.

127
00:05:07,940 --> 00:05:13,640
And then we again come over here we see that there are things in the queue we dequeue right.

128
00:05:13,640 --> 00:05:16,280
So again over here the length was set to one.

129
00:05:16,280 --> 00:05:17,300
Count is now zero.

130
00:05:17,300 --> 00:05:21,770
We come inside this VDC this and we it does not have any children.

131
00:05:21,770 --> 00:05:24,260
We increment count and now count is equal to length.

132
00:05:24,260 --> 00:05:26,750
So this also is going to be added to our right view.

133
00:05:26,750 --> 00:05:31,130
And this gives our answer which is 7183 and five.

134
00:05:31,130 --> 00:05:33,470
So this is the answer for our right view.

135
00:05:33,470 --> 00:05:37,940
Now let's also quickly discuss how we can build the left view with the same logic.

136
00:05:37,940 --> 00:05:39,680
So it's going to be pretty much similar.

137
00:05:39,680 --> 00:05:42,230
And I'm sure you must have solved it on your own.

138
00:05:42,230 --> 00:05:45,920
But just for completeness sake, let's discuss the left view also over here.

139
00:05:46,830 --> 00:05:49,590
Again, we are starting with the algorithm which we had previously.

140
00:05:49,590 --> 00:05:51,930
So I'm just removing current level from here.

141
00:05:51,930 --> 00:05:54,720
And I'm removing removing current level from here as well.

142
00:05:54,720 --> 00:05:56,100
And this also all right.

143
00:05:56,100 --> 00:05:58,350
And we have our left you array over here.

144
00:05:58,350 --> 00:05:59,910
So this is going to be the same.

145
00:05:59,910 --> 00:06:01,590
Only the check is going to be different.

146
00:06:01,590 --> 00:06:06,330
So inside this after enqueuing we are going to check if count is equal to one.

147
00:06:06,330 --> 00:06:08,970
So initially count is zero for every level right.

148
00:06:08,970 --> 00:06:15,150
So when we are inside and when we increment count once then for the first element count will always

149
00:06:15,150 --> 00:06:15,840
become one right.

150
00:06:15,840 --> 00:06:19,950
So if count is equal to one then we will just push it to our left array.

151
00:06:19,950 --> 00:06:20,820
So let's try.

152
00:06:20,820 --> 00:06:23,280
So initially we add seven to our queue.

153
00:06:23,280 --> 00:06:26,400
And then we come inside because there is something in our queue.

154
00:06:26,400 --> 00:06:28,680
Count is zero and length of the queue is one.

155
00:06:28,680 --> 00:06:31,440
Now we come inside over here because zero is less than one.

156
00:06:31,440 --> 00:06:36,720
We dequeue this seven and we are going to enqueue its children which is 11 and one.

157
00:06:36,720 --> 00:06:37,230
All right.

158
00:06:37,230 --> 00:06:42,000
And then over here again this push also I'm removing over here we are going to increment count.

159
00:06:42,000 --> 00:06:43,020
Count becomes one.

160
00:06:43,020 --> 00:06:45,450
Now we are checking whether count is equal to one.

161
00:06:45,450 --> 00:06:45,750
Yes.

162
00:06:45,750 --> 00:06:46,800
Count is equal to one.

163
00:06:46,800 --> 00:06:49,320
Therefore we are going to push this to our left view.

164
00:06:49,320 --> 00:06:50,730
So we get seven over here.

165
00:06:50,730 --> 00:06:52,290
And again we continue right.

166
00:06:52,290 --> 00:06:55,230
So we come over here we see that there are elements in the queue.

167
00:06:55,230 --> 00:06:56,310
So we come inside.

168
00:06:56,310 --> 00:07:00,330
Count is again changed to zero and the length of the queue is equal to two.

169
00:07:00,330 --> 00:07:01,380
And we proceed right.

170
00:07:01,380 --> 00:07:02,820
So again zero is less than two.

171
00:07:02,850 --> 00:07:03,840
So we come inside.

172
00:07:03,840 --> 00:07:05,040
We dequeue this one.

173
00:07:05,040 --> 00:07:05,370
All right.

174
00:07:05,370 --> 00:07:08,310
So 11 is dequeued and we enqueue its left and right.

175
00:07:08,310 --> 00:07:09,990
So only one child is there.

176
00:07:09,990 --> 00:07:13,080
So seven is enqueued and then count is incremented.

177
00:07:13,080 --> 00:07:14,370
So count becomes one.

178
00:07:14,370 --> 00:07:15,840
We are checking if count is equal to one.

179
00:07:15,840 --> 00:07:17,070
Yes count is equal to one.

180
00:07:17,070 --> 00:07:19,290
So this gets added to our left view array.

181
00:07:19,290 --> 00:07:21,150
So we push it to our left view array.

182
00:07:21,270 --> 00:07:25,890
Again we come over here we see there are things in in our um queue.

183
00:07:25,890 --> 00:07:26,160
Right.

184
00:07:26,160 --> 00:07:27,720
So we are over here in this part.

185
00:07:27,750 --> 00:07:29,370
The count is just one at this point.

186
00:07:29,370 --> 00:07:29,820
All right.

187
00:07:29,820 --> 00:07:32,940
So we come over here one is less than two.

188
00:07:32,970 --> 00:07:34,290
So again we come inside.

189
00:07:34,290 --> 00:07:35,490
We dequeue this.

190
00:07:35,490 --> 00:07:38,760
But at this point again one has children two and eight.

191
00:07:38,760 --> 00:07:42,060
So let's enqueue the children and then current becomes two.

192
00:07:42,060 --> 00:07:42,270
Right.

193
00:07:42,270 --> 00:07:43,470
So the count becomes two.

194
00:07:43,500 --> 00:07:45,030
So two is not equal to one.

195
00:07:45,030 --> 00:07:46,110
So we don't push this.

196
00:07:46,110 --> 00:07:46,560
All right.

197
00:07:46,560 --> 00:07:50,790
So at this point when we come over here two less than two that's falsy.

198
00:07:50,790 --> 00:07:52,470
And we come to this while loop.

199
00:07:52,470 --> 00:07:53,730
So this is how it proceeds.

200
00:07:53,730 --> 00:07:55,530
Now we have these three elements.

201
00:07:55,530 --> 00:07:56,340
Now let's proceed.

202
00:07:56,340 --> 00:07:58,560
Let's just clean this up a little bit.

203
00:07:59,760 --> 00:08:00,150
All right.

204
00:08:00,150 --> 00:08:03,570
So at this point again count is changed to zero.

205
00:08:03,570 --> 00:08:05,670
The length over here is equal to three.

206
00:08:05,670 --> 00:08:07,020
And then we come inside.

207
00:08:07,020 --> 00:08:08,610
So zero is less than three.

208
00:08:08,610 --> 00:08:12,420
We come inside VDC this and we are enqueueing its children.

209
00:08:12,420 --> 00:08:13,620
It does not have any children.

210
00:08:13,620 --> 00:08:17,220
Then we increment count to one and we check count is equal to one.

211
00:08:17,220 --> 00:08:18,390
So yes, we are taking this.

212
00:08:18,390 --> 00:08:19,440
So we put it over here.

213
00:08:19,440 --> 00:08:19,920
All right.

214
00:08:19,920 --> 00:08:21,480
We push it to our left view array.

215
00:08:21,690 --> 00:08:23,850
Again we are going to do this.

216
00:08:24,270 --> 00:08:26,970
We come over here and one is less than three.

217
00:08:26,970 --> 00:08:31,800
So we take out two and we enqueue its children which is just three at this point.

218
00:08:32,220 --> 00:08:33,840
And we increment count.

219
00:08:33,840 --> 00:08:36,000
So two and count is not one right.

220
00:08:36,000 --> 00:08:41,250
So we are not pushing to our left array and we get two less than three when we check this while loop

221
00:08:41,250 --> 00:08:41,610
condition.

222
00:08:41,610 --> 00:08:44,970
So we again come inside over here and we are going to dequeue.

223
00:08:44,970 --> 00:08:47,640
So we take this and we enqueue its children.

224
00:08:47,640 --> 00:08:49,020
So it does not have any children.

225
00:08:49,020 --> 00:08:53,010
Now we are checking whether and again we increment count.

226
00:08:53,010 --> 00:08:54,360
So count becomes three.

227
00:08:54,390 --> 00:08:55,800
We are checking if three is equal to one.

228
00:08:55,800 --> 00:08:56,880
No that's not true.

229
00:08:56,880 --> 00:08:58,560
So we come again over here now three.

230
00:08:58,560 --> 00:08:59,100
Less than three.

231
00:08:59,100 --> 00:08:59,790
That's falsy.

232
00:08:59,790 --> 00:09:01,230
So we come to this while loop.

233
00:09:01,230 --> 00:09:03,330
Again we have one element in our queue.

234
00:09:03,330 --> 00:09:04,680
So we come inside.

235
00:09:04,680 --> 00:09:07,230
And the length at this point is equal to one.

236
00:09:07,230 --> 00:09:08,670
So let's just clean this up.

237
00:09:08,670 --> 00:09:13,320
The length that this point is equal to one the count is again changed to zero now zero less than one.

238
00:09:13,320 --> 00:09:16,950
So we come inside VDC and its children.

239
00:09:16,950 --> 00:09:19,350
We add its children which is just five.

240
00:09:19,350 --> 00:09:21,150
And then we are incrementing count.

241
00:09:21,150 --> 00:09:22,290
So count becomes one.

242
00:09:22,290 --> 00:09:23,940
So yes one is equal to one.

243
00:09:23,940 --> 00:09:24,420
That's true.

244
00:09:24,420 --> 00:09:25,110
So we push.

245
00:09:25,110 --> 00:09:27,570
So this value over here is pushed to our left view.

246
00:09:27,570 --> 00:09:30,360
Now we we again come over here.

247
00:09:30,360 --> 00:09:32,160
One less than one is falsy right.

248
00:09:32,160 --> 00:09:33,660
So we come out of this while loop.

249
00:09:33,660 --> 00:09:36,240
We come over here and we check if there is something in the queue.

250
00:09:36,270 --> 00:09:41,970
Yes, we have this element in the queue again we come inside so count is changed to zero and length

251
00:09:41,970 --> 00:09:44,190
again is one and zero less than one.

252
00:09:44,190 --> 00:09:47,370
So we come inside VDC this element which is five.

253
00:09:48,110 --> 00:09:49,040
And its children.

254
00:09:49,040 --> 00:09:52,490
So there are no children to NQ and we increment count to one.

255
00:09:52,490 --> 00:09:54,320
Now we see that count is equal to one.

256
00:09:54,320 --> 00:09:57,320
Therefore we are pushing this value also to our left view.

257
00:09:57,320 --> 00:10:01,520
And we get we when we come over here one less than one.

258
00:10:01,520 --> 00:10:02,960
So that's falsy again.

259
00:10:02,960 --> 00:10:07,670
When we come over here there is nothing in our queue and we come out of the function call and this is

260
00:10:07,670 --> 00:10:08,270
our left view.

261
00:10:08,270 --> 00:10:13,370
Seven and then we have 11, then we have seven, then three and five.

262
00:10:13,370 --> 00:10:14,720
So this is the left view array.

263
00:10:14,720 --> 00:10:20,330
So you can see that both the right view and left view is very much similar to the level order traversal

264
00:10:20,330 --> 00:10:21,140
which we discussed.

265
00:10:21,170 --> 00:10:25,010
Now what about the time and space complexity of these solutions.

266
00:10:25,010 --> 00:10:30,020
The time complexity is going to be O of N because we are visiting every node one time.

267
00:10:30,020 --> 00:10:30,200
Right.

268
00:10:30,200 --> 00:10:32,120
So it's it's just breadth first search.

269
00:10:32,120 --> 00:10:34,940
So the time complexity is straightforward O of n.

270
00:10:34,940 --> 00:10:36,770
What about the space complexity.

271
00:10:37,250 --> 00:10:39,530
Now what are the things that take up space.

272
00:10:39,530 --> 00:10:41,750
We have the queue that takes up space.

273
00:10:41,750 --> 00:10:45,500
And we also have the array the output array right the left or right view.

274
00:10:45,500 --> 00:10:47,180
So this also takes up space.

275
00:10:47,420 --> 00:10:50,720
Now the queue can go up to size n by two.

276
00:10:50,720 --> 00:10:50,930
Right.

277
00:10:50,930 --> 00:10:55,550
Because we have seen that in the case of a full binary tree there can be n by two leaves.

278
00:10:55,550 --> 00:10:59,990
So that's why we can say that the queue takes space of the order of n by two.

279
00:11:00,020 --> 00:11:04,850
But when it comes to the output array, it's going to take space of the order of the number of levels.

280
00:11:04,850 --> 00:11:05,180
Right.

281
00:11:05,180 --> 00:11:11,150
So for every level either the leftmost if it's the left view or the rightmost if it's the right view

282
00:11:11,150 --> 00:11:13,430
will be there in the output arrays.

283
00:11:13,430 --> 00:11:19,190
So the number of elements is going to be less than n in the case of this left or right view right.

284
00:11:19,190 --> 00:11:22,550
So we don't need to consider this because this is going to be less than n.

285
00:11:22,550 --> 00:11:26,390
But when it comes to the queue it's going to have n by two elements.

286
00:11:26,390 --> 00:11:29,840
So the space complexity of this is going to be o of n by two.

287
00:11:29,840 --> 00:11:32,840
And because two is a constant, we can just avoid this.

288
00:11:32,840 --> 00:11:37,430
And we can say that the space complexity of this solution is of the order of n.

289
00:11:37,430 --> 00:11:41,960
So the time complexity is O of n and the space complexity is O of n.