1
00:00:00,770 --> 00:00:01,700
Hi everyone.

2
00:00:01,700 --> 00:00:05,840
In this question we are going to see how we can implement depth.

3
00:00:05,840 --> 00:00:07,370
First search for a graph.

4
00:00:07,370 --> 00:00:13,790
Now over here we are going to do it in both the ways we can either do DFS recursively or iteratively.

5
00:00:13,790 --> 00:00:15,230
So let's read the question.

6
00:00:15,230 --> 00:00:18,500
You are given a graph stored as an adjacency list.

7
00:00:18,500 --> 00:00:25,520
Write functions to traverse the graph using the depth first search approach recursively and iteratively.

8
00:00:25,520 --> 00:00:27,770
So we are going to do it in both the ways.

9
00:00:27,770 --> 00:00:33,170
As you traverse the graph, store the values of the vertices in an array and return this array.

10
00:00:33,170 --> 00:00:34,910
So let's go ahead and do this.

11
00:00:34,910 --> 00:00:39,020
And notice that over here it's given that the graph is stored as an adjacency list.

12
00:00:39,020 --> 00:00:41,240
So let's say this is the graph that we have.

13
00:00:41,240 --> 00:00:44,690
And this would be stored in the adjacency list in this manner.

14
00:00:44,690 --> 00:00:44,900
Right.

15
00:00:44,900 --> 00:00:46,880
We have all the six nodes over here.

16
00:00:46,880 --> 00:00:51,260
And then we have an array over here for each key where the array is the value.

17
00:00:51,260 --> 00:00:54,170
And this value over here is the neighbors right.

18
00:00:54,170 --> 00:00:56,420
For example A has the neighbors b and f.

19
00:00:56,420 --> 00:00:59,150
That's why this array over here has b and f.

20
00:00:59,150 --> 00:00:59,600
All right.

21
00:00:59,600 --> 00:01:01,610
So we have already seen this previously.

22
00:01:01,610 --> 00:01:04,490
Now let's go ahead and understand DFS first.

23
00:01:04,490 --> 00:01:07,460
And then we will see how we can implement this in our code.

24
00:01:07,460 --> 00:01:07,910
All right.

25
00:01:07,940 --> 00:01:15,740
Now the idea of DFS or depth first search or depth first traversal is that we visit a child node before

26
00:01:15,740 --> 00:01:17,750
we visit the neighbor of a particular node.

27
00:01:17,750 --> 00:01:19,010
So what does this mean.

28
00:01:19,010 --> 00:01:20,840
So let's try to understand this.

29
00:01:20,840 --> 00:01:26,870
Let's say we start traversing this graph over here at this node over here which is node A or vertex

30
00:01:26,870 --> 00:01:27,140
a.

31
00:01:27,680 --> 00:01:30,020
Now we go to its child.

32
00:01:30,020 --> 00:01:31,970
So the child of A is b.

33
00:01:31,970 --> 00:01:32,330
All right.

34
00:01:32,330 --> 00:01:36,710
So we go to the child and then we again go to the child of B.

35
00:01:36,710 --> 00:01:36,980
Right.

36
00:01:36,980 --> 00:01:38,930
We could have gone to the neighbor.

37
00:01:38,930 --> 00:01:40,430
The neighbor of B is F right.

38
00:01:40,430 --> 00:01:44,510
So that is what we did in the case of BFS or breadth first search.

39
00:01:44,510 --> 00:01:47,720
But over here we have to go to the child before the neighbor.

40
00:01:47,720 --> 00:01:51,890
So that is why we go from B to C which is the child of B, right.

41
00:01:51,890 --> 00:01:56,210
And after that we go to the child of C which is E, right.

42
00:01:56,210 --> 00:01:57,950
So I could have gone to D also.

43
00:01:57,950 --> 00:02:02,510
But in this case we are going to choose the child based on how it is stored.

44
00:02:02,510 --> 00:02:08,420
And you can see that in this, this array over here we are, we have e before D right.

45
00:02:08,420 --> 00:02:10,040
So B is already visited.

46
00:02:10,040 --> 00:02:11,480
So we are not going to go back.

47
00:02:11,480 --> 00:02:18,500
But of the child of the children of C we have D and E, but because over here we have stored e before

48
00:02:18,530 --> 00:02:20,270
D that's why we go e first.

49
00:02:20,270 --> 00:02:23,360
So if we had stored D before E we would have gone D first.

50
00:02:23,360 --> 00:02:24,950
So that does not matter.

51
00:02:24,950 --> 00:02:30,590
So we go to E and then from E we are going to go to its child which is D right.

52
00:02:31,100 --> 00:02:33,680
Again over here you can see we have D first right.

53
00:02:33,680 --> 00:02:36,620
So that is why we are going to D before we go to F.

54
00:02:36,620 --> 00:02:40,340
Now we see that D does not have any unvisited child.

55
00:02:40,340 --> 00:02:40,550
Right.

56
00:02:40,550 --> 00:02:42,800
So it does not have a child to visit.

57
00:02:42,800 --> 00:02:45,470
That's why we are going to visit the neighbor.

58
00:02:45,470 --> 00:02:47,360
So there is no child.

59
00:02:47,360 --> 00:02:48,380
So we go to the neighbor.

60
00:02:48,380 --> 00:02:51,410
So the neighbor of D is F right.

61
00:02:51,410 --> 00:02:55,040
So the neighbor of D is f because d is a child of E, right.

62
00:02:55,040 --> 00:02:56,750
So d is a child of e at this point.

63
00:02:56,750 --> 00:02:57,050
Right.

64
00:02:57,050 --> 00:02:58,160
So this is done.

65
00:02:58,160 --> 00:03:00,110
And then f is the neighbor of d.

66
00:03:00,110 --> 00:03:02,840
But first we try whether we have a child of d.

67
00:03:02,840 --> 00:03:04,460
So in this case we don't have.

68
00:03:04,460 --> 00:03:07,370
That's why we go to the neighbor of E which is f.

69
00:03:07,370 --> 00:03:09,020
So we go in this direction.

70
00:03:09,800 --> 00:03:14,180
And at this point you can see we have traversed or visited all the nodes.

71
00:03:14,180 --> 00:03:20,570
And if we were to print all the values as we visited the different nodes into an array, it would look

72
00:03:20,570 --> 00:03:24,230
like this a and then from A we went to B.

73
00:03:24,230 --> 00:03:30,590
From B we went to C, from C, we went to E, from E we went to D, and then from there we went to F,

74
00:03:30,590 --> 00:03:33,020
which is the neighbor of E, right.

75
00:03:33,020 --> 00:03:35,060
Because D did not have any child.

76
00:03:35,060 --> 00:03:37,910
So this is how depth first search works.

77
00:03:37,910 --> 00:03:42,200
So we go as deep as possible before we start going wide.

78
00:03:42,200 --> 00:03:43,310
So that's the idea.

79
00:03:43,310 --> 00:03:46,670
Or we visit children before we visit neighbors.

80
00:03:46,670 --> 00:03:47,210
All right.

81
00:03:47,210 --> 00:03:48,590
So that is DFS.

82
00:03:48,590 --> 00:03:53,540
And then another important thing to keep in mind is there is no unique DFS for a given graph.

83
00:03:53,540 --> 00:03:53,840
Right.

84
00:03:53,840 --> 00:04:00,230
So there would be nothing wrong if instead of going from C to E, if I had taken the choice of going

85
00:04:00,230 --> 00:04:06,410
from C to D, and again, we made that choice based on how we had stored the different children in this

86
00:04:06,410 --> 00:04:07,070
array over here.

87
00:04:07,070 --> 00:04:11,870
So the important thing is there is no unique DFS for a given graph.

88
00:04:11,870 --> 00:04:17,240
The the the output array which we are getting in this case depends on the choices that we have made.

89
00:04:17,240 --> 00:04:21,050
So we can have many answers if you do a DFS for a particular graph.

90
00:04:21,050 --> 00:04:21,710
All right.

91
00:04:21,710 --> 00:04:24,980
So let's now go ahead and see how we can implement this.

92
00:04:24,980 --> 00:04:27,650
First we will try to implement this recursively.

93
00:04:27,650 --> 00:04:29,030
So let's go ahead and do this.

94
00:04:29,060 --> 00:04:31,340
We are going to implement DFS recursively.

95
00:04:31,340 --> 00:04:33,500
Now for this we will need a function.

96
00:04:33,500 --> 00:04:35,990
So let's call this function f.

97
00:04:35,990 --> 00:04:39,860
And we will be calling this function recursively for every node.

98
00:04:39,860 --> 00:04:46,610
Now initially let's say we are calling this function for the node a and we have to pass the graph to

99
00:04:46,610 --> 00:04:46,910
it.

100
00:04:46,910 --> 00:04:50,150
And we also need to pass an output array to it.

101
00:04:50,150 --> 00:04:56,150
And we also have to have a visited object or a hash table to see whether we have visited a particular

102
00:04:56,150 --> 00:04:57,710
vertex or not.

103
00:04:57,710 --> 00:04:58,280
All right.

104
00:04:58,280 --> 00:05:03,110
So let's say we initially call this function and we have it in our call stack.

105
00:05:03,110 --> 00:05:09,260
So we have to graph with vertex A in our call stack so that we will keep tracking the call stack also

106
00:05:09,260 --> 00:05:12,830
over here so that we get an understanding of the recursive function.

107
00:05:12,830 --> 00:05:13,430
All right.

108
00:05:13,880 --> 00:05:16,640
And again we need an output array which we have over here.

109
00:05:16,640 --> 00:05:21,380
Initially the output array is empty and the visited object is also empty.

110
00:05:21,410 --> 00:05:25,910
Now at this point we have called graph with vertex a.

111
00:05:25,910 --> 00:05:26,540
All right.

112
00:05:26,540 --> 00:05:29,090
So we are inside the trial function.

113
00:05:29,090 --> 00:05:33,350
And what we will do is we will push that value to our output array.

114
00:05:33,350 --> 00:05:35,540
And we will mark it as visited.

115
00:05:35,540 --> 00:05:38,960
So we have visited A and we have pushed it to our output array.

116
00:05:39,260 --> 00:05:39,860
All right.

117
00:05:39,860 --> 00:05:45,860
Now what we do is we will try to identify the neighbors of this particular vertex.

118
00:05:45,890 --> 00:05:46,430
All right.

119
00:05:46,430 --> 00:05:49,490
So the neighbors of A are b and f.

120
00:05:49,490 --> 00:05:54,140
And for this we make use of the graph which is stored as an adjacency list over here.

121
00:05:54,140 --> 00:05:55,640
So we take the neighbors.

122
00:05:55,640 --> 00:06:03,470
And if a particular neighbor is not yet visited we will recursively call the function passing that particular

123
00:06:03,470 --> 00:06:04,430
neighbor vertex.

124
00:06:04,430 --> 00:06:05,750
So this is how this works.

125
00:06:05,750 --> 00:06:07,790
So at this point we have b.

126
00:06:07,820 --> 00:06:09,620
We see that it is not yet visited.

127
00:06:09,620 --> 00:06:13,310
So we will call the try function recursively for b.

128
00:06:14,030 --> 00:06:14,540
All right.

129
00:06:14,540 --> 00:06:17,630
And once we are and again this is a DFS right.

130
00:06:17,630 --> 00:06:19,340
So we will go depth first.

131
00:06:19,340 --> 00:06:25,880
But once we come back to this level we have still an option to call the trial function for F as well.

132
00:06:25,880 --> 00:06:28,340
Because at this point f is not yet visited.

133
00:06:28,340 --> 00:06:32,660
So I'm just writing F over here so that we can visually track the recursive call.

134
00:06:32,660 --> 00:06:32,960
All right.

135
00:06:32,960 --> 00:06:35,030
So it so that it does not get confused.

136
00:06:35,030 --> 00:06:41,960
So when we come back the idea is that if f is not yet visited then at this point we will call f again

137
00:06:41,960 --> 00:06:44,420
with f vertex f at that point.

138
00:06:44,420 --> 00:06:44,930
All right.

139
00:06:44,930 --> 00:06:47,150
So at this point we are again back over here.

140
00:06:47,150 --> 00:06:49,490
And vertex at this point is b.

141
00:06:49,520 --> 00:06:53,840
Now we push b to our output array and we mark B as visited.

142
00:06:53,840 --> 00:06:57,170
And then we are going to identify the neighbors of B at this point.

143
00:06:57,170 --> 00:06:57,440
Right.

144
00:06:57,440 --> 00:06:59,870
So for this we make use of the adjacency list.

145
00:06:59,870 --> 00:07:03,620
And we see that the neighbors are A and C a is already visited.

146
00:07:03,620 --> 00:07:08,330
So we are going to call recursively the trial function for vertex c.

147
00:07:08,330 --> 00:07:10,190
So that is traffic c at this point.

148
00:07:10,190 --> 00:07:10,760
All right.

149
00:07:11,240 --> 00:07:12,710
So we come again over here.

150
00:07:12,710 --> 00:07:17,720
Now at this point when we are at this line we are going to push C to our output array.

151
00:07:17,720 --> 00:07:19,940
And we will mark C as visited.

152
00:07:19,940 --> 00:07:24,800
And then we are going to identify the neighbors of C which is B, E and D.

153
00:07:24,800 --> 00:07:27,020
And among these b is already visited.

154
00:07:27,020 --> 00:07:29,000
So e and D are not visited.

155
00:07:29,000 --> 00:07:29,330
Right.

156
00:07:29,330 --> 00:07:36,020
So we are going to call f function this trap function recursively with e and we have the option to call

157
00:07:36,020 --> 00:07:36,860
it with d.

158
00:07:36,950 --> 00:07:38,600
So again this is DFS.

159
00:07:38,600 --> 00:07:39,830
We go depth first.

160
00:07:39,830 --> 00:07:45,980
But once we are back over here if D is not yet visited then we have the option to call the trap function

161
00:07:45,980 --> 00:07:48,290
with D at that point when we are coming back.

162
00:07:48,290 --> 00:07:48,800
All right.

163
00:07:48,800 --> 00:07:50,990
So we call trap with E again.

164
00:07:50,990 --> 00:07:52,370
We come inside the trap function.

165
00:07:52,370 --> 00:07:56,600
We are going to push E to our output array and we mark E as visited.

166
00:07:56,600 --> 00:08:01,220
Now we are going to identify the neighbors of E which is D, C and f.

167
00:08:01,220 --> 00:08:04,220
Now among this we can see that only c is visited, right.

168
00:08:04,220 --> 00:08:07,400
So we can call the trap function for d and f.

169
00:08:07,400 --> 00:08:09,260
So we first call it for d.

170
00:08:09,490 --> 00:08:11,740
And then we have the option to call it for f.

171
00:08:11,740 --> 00:08:13,210
So I mark F over here.

172
00:08:13,210 --> 00:08:18,790
And then again when we do that we push D and we mark D as visited.

173
00:08:18,790 --> 00:08:22,510
And then we are going to check the neighbors of D.

174
00:08:22,510 --> 00:08:24,820
So the neighbors of D are C and E.

175
00:08:24,820 --> 00:08:26,890
And you can see that both of them are visited.

176
00:08:26,890 --> 00:08:27,160
Right.

177
00:08:27,160 --> 00:08:30,070
So no recursive call is going to happen.

178
00:08:30,070 --> 00:08:34,450
So this call where we call the function passing D is done right.

179
00:08:34,450 --> 00:08:40,150
So this is done again there is no neighbor which is unvisited which we checked over here using the adjacency

180
00:08:40,150 --> 00:08:40,510
list.

181
00:08:40,510 --> 00:08:42,820
So at this point this call is over right.

182
00:08:42,820 --> 00:08:46,450
So this was done where we pushed D and marked it as visited.

183
00:08:46,450 --> 00:08:49,960
We identified the neighbors of D and then we checked for the neighbors.

184
00:08:49,960 --> 00:08:53,830
If they were not visited we saw there is none which is not visited.

185
00:08:53,830 --> 00:08:55,270
So this call is over right.

186
00:08:55,270 --> 00:08:58,600
So this call is over and the call stack is cleared.

187
00:08:58,600 --> 00:09:00,250
Now we come back over here.

188
00:09:00,730 --> 00:09:02,800
We had the option to call for F as well.

189
00:09:02,800 --> 00:09:06,550
Right at this point where we were checking for the neighbors of E.

190
00:09:06,580 --> 00:09:08,290
So we are done with this.

191
00:09:08,290 --> 00:09:09,880
And C is already visited.

192
00:09:09,880 --> 00:09:13,870
Now we will iterate to f, we see that f is not yet visited.

193
00:09:13,870 --> 00:09:16,090
So we will call trough with f.

194
00:09:16,090 --> 00:09:18,730
So we call trough with f at this point.

195
00:09:18,730 --> 00:09:21,040
So we are again inside the trough function.

196
00:09:21,040 --> 00:09:25,150
We push f to the output array and we mark f as visited.

197
00:09:25,150 --> 00:09:25,690
All right.

198
00:09:25,690 --> 00:09:26,980
So that is done.

199
00:09:26,980 --> 00:09:29,590
And that brings us to the end of this call as well.

200
00:09:29,590 --> 00:09:31,210
So this is also done right.

201
00:09:31,210 --> 00:09:34,660
Because all of these neighbors A and D are already visited.

202
00:09:34,660 --> 00:09:36,280
So this is not going to execute.

203
00:09:36,280 --> 00:09:38,140
So that call of trough is done.

204
00:09:38,140 --> 00:09:39,490
So we return right.

205
00:09:39,490 --> 00:09:42,610
So f is done D is done and we come back over here.

206
00:09:42,610 --> 00:09:46,750
So at this point the call the depth first call from here is done.

207
00:09:46,750 --> 00:09:47,950
So this is also done right.

208
00:09:47,950 --> 00:09:52,450
So we have the option now to increment and go to D.

209
00:09:52,450 --> 00:09:55,360
But we can see that D is already visited at this point.

210
00:09:55,360 --> 00:09:57,430
So we are not going to call D again.

211
00:09:57,430 --> 00:09:57,640
Right.

212
00:09:57,640 --> 00:09:59,890
We are not going to go with D.

213
00:09:59,890 --> 00:10:01,960
And then this call is done.

214
00:10:01,960 --> 00:10:02,140
Right.

215
00:10:02,140 --> 00:10:06,190
So this was part of the this going deep was part of this call traffic.

216
00:10:06,220 --> 00:10:06,520
Right.

217
00:10:06,520 --> 00:10:08,410
So we were checking the neighbors of C.

218
00:10:08,410 --> 00:10:10,600
So the neighbors of C are done now right.

219
00:10:10,600 --> 00:10:11,770
So this call is also done.

220
00:10:11,770 --> 00:10:12,460
It returns.

221
00:10:12,460 --> 00:10:16,900
And then this call is also done because this call was part of B call.

222
00:10:16,900 --> 00:10:18,040
So all of this is done.

223
00:10:18,040 --> 00:10:19,120
So B is done.

224
00:10:19,120 --> 00:10:22,210
We have the option to call the trial function with f.

225
00:10:22,210 --> 00:10:24,430
But we can see that f is already visited.

226
00:10:24,430 --> 00:10:26,080
So this does not happen.

227
00:10:26,080 --> 00:10:29,620
And then we come back and this call is also done right.

228
00:10:29,620 --> 00:10:32,140
So we come out of the call stack.

229
00:10:32,140 --> 00:10:34,030
So the call stack is empty at this point.

230
00:10:34,030 --> 00:10:35,410
Again why is this out.

231
00:10:35,410 --> 00:10:41,020
Because we pushed a and then we checked for the neighbors of A which is B and F.

232
00:10:41,020 --> 00:10:43,030
And then we went depth first.

233
00:10:43,030 --> 00:10:43,300
Right.

234
00:10:43,300 --> 00:10:46,930
So we took the child which is B and we went in this direction.

235
00:10:46,930 --> 00:10:50,590
So when we come back we see that f is already visited.

236
00:10:50,590 --> 00:10:55,000
So that's why when we got back to here we are not going to call the trap function with f.

237
00:10:55,000 --> 00:10:58,750
So once this step is done, this step is done and this step is done right.

238
00:10:58,750 --> 00:11:03,520
So that was checking the children and if not visited calling the trap function recursively.

239
00:11:03,520 --> 00:11:04,480
So that is also done.

240
00:11:04,480 --> 00:11:07,600
So once this is done this call is done right.

241
00:11:07,600 --> 00:11:09,760
So this call was with vertex A.

242
00:11:09,760 --> 00:11:10,750
So this is also done.

243
00:11:10,750 --> 00:11:13,960
So that's why trough A is removed from the call stack.

244
00:11:13,960 --> 00:11:16,060
So the call stack is empty and we're done.

245
00:11:16,060 --> 00:11:20,800
So we get our output array which is a b c e d and f.

246
00:11:20,800 --> 00:11:24,130
So this is how the DFS recursive function works.

247
00:11:24,130 --> 00:11:28,990
Now let's take a quick look at the complexity analysis of this solution.

248
00:11:28,990 --> 00:11:35,410
Now the time complexity of this solution is going going to be of the order of v plus E where v is the

249
00:11:35,410 --> 00:11:38,290
number of vertices and e is the number of edges.

250
00:11:38,320 --> 00:11:39,250
Now why is this.

251
00:11:39,250 --> 00:11:43,390
So we are traversing or visiting every vertex once right.

252
00:11:43,390 --> 00:11:45,760
So for this we have v over here right.

253
00:11:45,760 --> 00:11:48,160
So we are traversing every vertex at least once.

254
00:11:48,160 --> 00:11:50,500
So we have to do v operations.

255
00:11:50,500 --> 00:11:55,390
Or we can say that we have to call the travel function v times right.

256
00:11:55,390 --> 00:11:58,390
For each vertex we have to call it at least once.

257
00:11:58,390 --> 00:12:00,880
So we have to call it once exactly for each vertex.

258
00:12:00,880 --> 00:12:01,240
Right.

259
00:12:01,240 --> 00:12:03,280
So we are doing v operations over here.

260
00:12:03,280 --> 00:12:08,440
And then over here when we are checking whether the neighbor is visited or not.

261
00:12:08,440 --> 00:12:10,660
So we are doing this two e times.

262
00:12:10,660 --> 00:12:10,870
Right.

263
00:12:10,870 --> 00:12:17,290
We are doing it two e times because for every vertex we have to do it the number of times equivalent

264
00:12:17,290 --> 00:12:19,660
to the size of the array for that particular vertex.

265
00:12:19,660 --> 00:12:22,270
So if we add all of these up what is it that we are getting.

266
00:12:22,270 --> 00:12:28,180
Let's try 123456789 1011 1213 and 14.

267
00:12:28,180 --> 00:12:32,170
So this over here is going to do 14 operations.

268
00:12:32,170 --> 00:12:37,570
And this 14 is nothing but two times seven where seven is the number of edges.

269
00:12:37,570 --> 00:12:42,940
So that is why we can say that the time complexity is of the order of V plus two e.

270
00:12:42,970 --> 00:12:45,850
You can say two e over here, but then two is a constant.

271
00:12:45,850 --> 00:12:47,080
So we can just avoid that.

272
00:12:47,080 --> 00:12:50,650
And we get that the time complexity is O of v plus e.

273
00:12:50,890 --> 00:12:56,290
Again remember the for loop is operating as many times as the number of children, which is nothing

274
00:12:56,290 --> 00:12:58,120
but the number of edges over here.

275
00:12:58,120 --> 00:12:58,420
Right.

276
00:12:58,420 --> 00:13:01,180
So again we have to check whether it is visited or not.

277
00:13:01,180 --> 00:13:05,800
Even though it's visited, we still have to check when we encounter a particular node again, we have

278
00:13:05,800 --> 00:13:09,100
to still make an operation and see whether it is visited or not.

279
00:13:09,330 --> 00:13:14,970
So the number of operations which is happening over here, across all the calls is equal to two e.

280
00:13:15,030 --> 00:13:17,490
And then we remove the constant two.

281
00:13:17,520 --> 00:13:22,260
That's why we get that the time complexity over here is of the order of V plus e.

282
00:13:23,210 --> 00:13:25,310
Now, what about the space complexity?

283
00:13:25,460 --> 00:13:29,420
The space complexity over here is going to be of the order of V.

284
00:13:29,450 --> 00:13:30,440
Why is that so?

285
00:13:30,470 --> 00:13:32,540
What are the different things that consume space?

286
00:13:32,540 --> 00:13:36,530
Over here we have the output array right which will have v elements.

287
00:13:36,530 --> 00:13:42,560
We have the visited object which also will have v number of key value pairs.

288
00:13:42,560 --> 00:13:44,450
And then we have the call stack right.

289
00:13:44,450 --> 00:13:48,920
Even the call stack in the worst case is going to take order of v space.

290
00:13:48,920 --> 00:13:49,310
Right.

291
00:13:49,310 --> 00:13:55,070
So again even if we did not want the output array then also the space complexity will be O of V because

292
00:13:55,070 --> 00:13:56,330
we have the visited object.

293
00:13:56,330 --> 00:13:59,930
And then even if you just look at the call stack in the worst case.

294
00:13:59,930 --> 00:14:04,460
And remember whenever we have a big O analysis, we are giving the worst case, right?

295
00:14:04,460 --> 00:14:09,710
So the call stack in the worst case will look something will look something like this for an array.

296
00:14:09,710 --> 00:14:15,650
So for a graph that looks something like this where a is pointing to b, b is pointing to c, C is pointing

297
00:14:15,680 --> 00:14:18,800
to d, d is pointing to e, and e is pointing to f.

298
00:14:18,800 --> 00:14:23,600
So if this is the case, then when we start from a we will go all the way till here.

299
00:14:23,600 --> 00:14:23,870
Right.

300
00:14:23,870 --> 00:14:27,830
So the call stack in this case will have v number of calls.

301
00:14:27,830 --> 00:14:28,040
Right.

302
00:14:28,040 --> 00:14:31,550
So in this case the call stack also will take O of v space.

303
00:14:31,550 --> 00:14:37,820
That's why we can say that the space complexity of this solution is O of v into a constant.

304
00:14:37,820 --> 00:14:38,210
Right.

305
00:14:38,210 --> 00:14:42,890
And then we just remove the constant and we get that the space complexity is O of V.