1
00:00:00,430 --> 00:00:01,360
Welcome back.

2
00:00:01,360 --> 00:00:07,090
So we have successfully returned the four instance methods for breadth first traversal and depth first

3
00:00:07,090 --> 00:00:07,840
traversal.

4
00:00:07,840 --> 00:00:08,320
All right.

5
00:00:08,350 --> 00:00:11,350
Now let's take some sample input and walk through the code.

6
00:00:11,350 --> 00:00:13,810
And this is an important step in interviews as well.

7
00:00:13,810 --> 00:00:16,720
So when you do coding interviews you will be asked to do this.

8
00:00:16,720 --> 00:00:17,110
All right.

9
00:00:17,110 --> 00:00:20,350
So let's get started with the breadth first traversal approach.

10
00:00:20,350 --> 00:00:22,180
So we are inside this function.

11
00:00:22,180 --> 00:00:24,910
We check whether the binary search tree is empty.

12
00:00:24,940 --> 00:00:27,730
If it's empty we just return an empty array.

13
00:00:27,760 --> 00:00:31,960
Now if not we go ahead and we initialize an array and a queue.

14
00:00:31,960 --> 00:00:34,960
Now remember over here we are implementing the queue as an array.

15
00:00:34,960 --> 00:00:36,550
But that's not the best way.

16
00:00:36,550 --> 00:00:39,130
So we are just doing that over here to save time.

17
00:00:39,130 --> 00:00:44,050
And because that's not the uh, central center part of the question which we are dealing over here,

18
00:00:44,050 --> 00:00:46,480
right over here, we are dealing with breadth first traversal.

19
00:00:46,480 --> 00:00:52,090
Now to get the best performance in terms of time complexity, we have to implement the queue as a linked

20
00:00:52,090 --> 00:00:52,540
list.

21
00:00:52,540 --> 00:00:53,020
All right.

22
00:00:53,050 --> 00:00:54,730
Now we have a variable node.

23
00:00:54,730 --> 00:00:57,280
And this is pointing to the root at this point.

24
00:00:57,280 --> 00:00:57,760
All right.

25
00:00:57,790 --> 00:01:01,870
Now we push this node to the uh queue.

26
00:01:01,870 --> 00:01:02,770
So we have a queue.

27
00:01:02,770 --> 00:01:04,360
So let's let this be the queue.

28
00:01:04,360 --> 00:01:05,950
Now it depends on the question.

29
00:01:05,950 --> 00:01:08,080
You can either push the node or you can push the value.

30
00:01:08,080 --> 00:01:09,220
It depends on the question.

31
00:01:09,220 --> 00:01:10,870
So over here we are pushing the node.

32
00:01:10,870 --> 00:01:13,510
So we have the node 76 in our queue.

33
00:01:13,510 --> 00:01:15,580
And then we have this while loop right.

34
00:01:15,580 --> 00:01:18,130
So now the length of the queue is greater than zero.

35
00:01:18,130 --> 00:01:20,410
So we are inside the while loop.

36
00:01:20,410 --> 00:01:23,200
And then we say node is equal to q dot shift.

37
00:01:23,200 --> 00:01:25,480
So we are taking the first element out right.

38
00:01:25,480 --> 00:01:26,830
So we are taking this out.

39
00:01:27,370 --> 00:01:31,450
And again remember we are we we are taking this out from the beginning of the array.

40
00:01:31,450 --> 00:01:35,020
So that's why we ideally should be implementing this with a linked list.

41
00:01:35,020 --> 00:01:39,070
Because that will give us an O of one time complexity if this was a linked list.

42
00:01:39,070 --> 00:01:39,580
All right.

43
00:01:39,580 --> 00:01:42,250
So this is the this is an array at this point.

44
00:01:42,250 --> 00:01:42,520
Right.

45
00:01:42,520 --> 00:01:47,230
So again just mention that to your interviewer that you're doing this as an array to save time.

46
00:01:47,230 --> 00:01:50,320
Now we take out this 76 and we push it to the array.

47
00:01:50,320 --> 00:01:51,310
So we have an array.

48
00:01:51,310 --> 00:01:53,110
Let me just call it a over here.

49
00:01:53,110 --> 00:01:54,880
And we push this to the array.

50
00:01:54,880 --> 00:01:58,270
Now again you can either push the node or the value depends on the question.

51
00:01:58,270 --> 00:02:00,400
Now over here you have 76.

52
00:02:00,400 --> 00:02:04,330
Then you enqueue or you push into the queue right.

53
00:02:04,330 --> 00:02:06,130
It's left and right children.

54
00:02:06,130 --> 00:02:08,620
So over here this is the node.

55
00:02:08,620 --> 00:02:09,580
It's left is 50.

56
00:02:09,580 --> 00:02:10,930
So we put 50 over here.

57
00:02:10,930 --> 00:02:12,580
And this has been taken out already right.

58
00:02:12,580 --> 00:02:13,390
We put it over here.

59
00:02:13,390 --> 00:02:16,990
Now we push to the queue 50 and then 80.

60
00:02:17,650 --> 00:02:18,160
All right.

61
00:02:18,160 --> 00:02:21,820
Now again we come back over here and we see that the queue is not empty.

62
00:02:21,820 --> 00:02:24,220
So we take 50 and we put it into the array.

63
00:02:24,220 --> 00:02:25,720
So that's happening over here.

64
00:02:25,720 --> 00:02:28,540
We take 50 and then we put it, we push it into the array.

65
00:02:28,540 --> 00:02:29,800
Then we are over here.

66
00:02:29,800 --> 00:02:31,660
And then its child 43 is there.

67
00:02:31,660 --> 00:02:33,010
So we put that into the queue.

68
00:02:33,040 --> 00:02:34,150
We have 43 over here.

69
00:02:34,150 --> 00:02:37,540
Now again we come over here we see that the queue is not empty.

70
00:02:37,540 --> 00:02:39,130
So we take 80.

71
00:02:39,160 --> 00:02:42,700
We take it out from the queue using the dot shift operation over here.

72
00:02:42,700 --> 00:02:47,800
And we push it to the array and we are at 80 and its children 78 and 90.

73
00:02:47,830 --> 00:02:48,160
Right.

74
00:02:48,160 --> 00:02:50,920
These two are pushed into the queue over here.

75
00:02:50,920 --> 00:02:53,920
So we have 78 and 90.

76
00:02:53,920 --> 00:02:55,510
Let me just write it like this over here.

77
00:02:55,510 --> 00:02:59,110
And then again we come over here, we see that the queue is not empty.

78
00:02:59,140 --> 00:03:03,760
We take 43, push it to the array and and 43 does not have any children.

79
00:03:03,760 --> 00:03:05,380
Again we come over here.

80
00:03:05,380 --> 00:03:06,400
The queue is not empty.

81
00:03:06,430 --> 00:03:10,300
We take 78, push it to the array and it does not have any children.

82
00:03:10,300 --> 00:03:16,180
Again we come over here and we take 90 and we push it to the uh array.

83
00:03:16,180 --> 00:03:18,250
And it does not have any children.

84
00:03:18,250 --> 00:03:20,350
So at this point the queue is empty.

85
00:03:20,350 --> 00:03:22,420
So q dot length is not greater than zero.

86
00:03:22,420 --> 00:03:24,790
So we come out of it and we return this array.

87
00:03:24,790 --> 00:03:27,400
So this is the breadth first traversal approach.

88
00:03:27,400 --> 00:03:28,690
So we have 76.

89
00:03:28,690 --> 00:03:29,740
That's this over here.

90
00:03:29,740 --> 00:03:34,960
Then we have 50 and 8050 and 80 and then 4378 and 90.

91
00:03:34,960 --> 00:03:37,540
So this is how we implement BFS.

92
00:03:37,690 --> 00:03:41,140
Let's now look at the DFS in order traversal.

93
00:03:41,140 --> 00:03:42,940
All right with the same binary search tree.

94
00:03:42,940 --> 00:03:45,130
So let's say we have called this function.

95
00:03:45,130 --> 00:03:46,330
Now we are inside this.

96
00:03:46,330 --> 00:03:50,020
Now over here we are checking whether the binary search tree is empty.

97
00:03:50,020 --> 00:03:51,430
And we see it's not empty.

98
00:03:51,430 --> 00:03:54,640
So we come over here and we have an array.

99
00:03:54,850 --> 00:03:58,480
I'm just writing it as a we initialize it and it's an empty array at this point.

100
00:03:58,480 --> 00:04:00,190
And then we have a variable current.

101
00:04:00,190 --> 00:04:03,190
So current is pointing to the root node at this point.

102
00:04:03,190 --> 00:04:06,280
Now at this point we have this function again it's not called.

103
00:04:06,280 --> 00:04:08,710
And over here we call the function.

104
00:04:08,710 --> 00:04:11,350
So let me just write the call stack over here.

105
00:04:11,350 --> 00:04:14,680
And I will just write it so that we can keep track of it.

106
00:04:14,680 --> 00:04:16,210
Because this is a recursive solution.

107
00:04:16,210 --> 00:04:18,280
So we are calling the function.

108
00:04:18,280 --> 00:04:22,960
And the node which is passed over here is the current node which is 76 at this point.

109
00:04:22,960 --> 00:04:23,290
Right.

110
00:04:23,290 --> 00:04:25,150
So let me just write this like this over here.

111
00:04:25,150 --> 00:04:31,330
1276 now over here, we are inside this function right now we are checking if it has a left node.

112
00:04:31,330 --> 00:04:33,700
So node dot left at this point is truthy.

113
00:04:33,700 --> 00:04:37,420
So we call again the function with this node 50 over here.

114
00:04:37,420 --> 00:04:39,340
So let me add that to our call stack.

115
00:04:39,340 --> 00:04:43,120
So again we have traf with the node 50 at this point.

116
00:04:43,570 --> 00:04:46,000
Now we are again inside the function graph.

117
00:04:46,000 --> 00:04:47,200
And the node is 50 right.

118
00:04:47,200 --> 00:04:48,370
So over here.

119
00:04:48,370 --> 00:04:50,410
So from 76 we came to 50.

120
00:04:50,410 --> 00:04:54,160
Now again inside this we are checking whether node dot left is truthy.

121
00:04:54,160 --> 00:04:57,280
Yes node dot left is truthy because you have 43 over here.

122
00:04:57,280 --> 00:04:59,650
So again we call traf with 43.

123
00:04:59,650 --> 00:05:00,010
So let me.

124
00:05:00,130 --> 00:05:03,790
Write that over here we call the trap function with 43 at this point.

125
00:05:03,820 --> 00:05:05,950
Now again we are inside this function over here.

126
00:05:05,950 --> 00:05:06,160
Right.

127
00:05:06,160 --> 00:05:07,780
So let me just clear this up.

128
00:05:09,580 --> 00:05:09,850
All right.

129
00:05:09,850 --> 00:05:10,900
So we are again over here.

130
00:05:10,900 --> 00:05:13,420
Now we are checking if node dot left is truthy.

131
00:05:13,420 --> 00:05:14,590
But this is null right.

132
00:05:14,590 --> 00:05:15,460
This is null.

133
00:05:15,460 --> 00:05:17,530
It's it does not have any children right.

134
00:05:17,530 --> 00:05:18,610
So this is null and null.

135
00:05:18,610 --> 00:05:20,290
So this is not truthy.

136
00:05:20,290 --> 00:05:20,440
Right.

137
00:05:20,440 --> 00:05:21,520
So it does not go over here.

138
00:05:21,520 --> 00:05:24,670
Then we come over here and we do array dot push node.

139
00:05:24,670 --> 00:05:26,170
So the current node is 43.

140
00:05:26,170 --> 00:05:27,700
So we push this to the array.

141
00:05:27,700 --> 00:05:28,870
So I'm just writing 43.

142
00:05:28,870 --> 00:05:32,440
Over here you can either push the node or the value depending on the question.

143
00:05:32,440 --> 00:05:34,360
So we are writing 43 over here.

144
00:05:34,360 --> 00:05:36,430
Now we come to the next line of the code.

145
00:05:36,430 --> 00:05:39,250
We are checking whether node dot right is truthy.

146
00:05:39,250 --> 00:05:40,240
But it's not right.

147
00:05:40,240 --> 00:05:41,200
There is no child over here.

148
00:05:41,200 --> 00:05:42,160
So this is falsy.

149
00:05:42,160 --> 00:05:43,570
So this does not execute.

150
00:05:43,570 --> 00:05:45,310
And we come out of this function right.

151
00:05:45,310 --> 00:05:48,340
So this call over here is removed from the call stack.

152
00:05:48,340 --> 00:05:51,370
And we are back with with this call right at 50.

153
00:05:51,370 --> 00:05:55,000
So when we had traversed 50 again let me just clear this up.

154
00:05:55,000 --> 00:06:00,130
So at this point when we are calling the function with 50, we are done with this line.

155
00:06:00,130 --> 00:06:00,340
Right.

156
00:06:00,340 --> 00:06:02,320
So we went left and we came back.

157
00:06:02,320 --> 00:06:04,030
Now we do array dot push node.

158
00:06:04,030 --> 00:06:06,640
So this 50 over here is pushed into the array.

159
00:06:06,640 --> 00:06:10,570
And then we we say we check whether node dot right is truthy.

160
00:06:10,570 --> 00:06:12,070
In this case this is null right.

161
00:06:12,070 --> 00:06:13,360
So this is not truthy.

162
00:06:13,360 --> 00:06:15,250
So this also does not get executed.

163
00:06:15,250 --> 00:06:17,020
And we come we come out of the function.

164
00:06:17,020 --> 00:06:19,150
So this call is also done right.

165
00:06:19,150 --> 00:06:24,610
So now we are in the trough call where we did the call with 76 as the node.

166
00:06:24,610 --> 00:06:24,880
Right.

167
00:06:24,880 --> 00:06:28,120
So we are done with the left part over here.

168
00:06:28,120 --> 00:06:29,110
So this is done.

169
00:06:29,110 --> 00:06:32,050
Now we come over here right because we just returned this.

170
00:06:32,050 --> 00:06:33,370
So that's why this is done.

171
00:06:33,370 --> 00:06:36,730
Now the current node is 76 and we push this to the array.

172
00:06:36,790 --> 00:06:38,710
So let me write 76 over here.

173
00:06:38,710 --> 00:06:40,540
And then we go to the right.

174
00:06:40,540 --> 00:06:43,210
So we check if node dot right is truthy.

175
00:06:43,210 --> 00:06:44,140
Yes it's truthy.

176
00:06:44,140 --> 00:06:46,570
So we come over here and we come over here.

177
00:06:46,570 --> 00:06:49,840
And we again add to the call stack.

178
00:06:49,840 --> 00:06:49,990
Right.

179
00:06:49,990 --> 00:06:52,270
So we have traversed now with 80.

180
00:06:52,990 --> 00:06:54,340
So we call this with 80.

181
00:06:55,210 --> 00:06:59,170
Now at this point again what we come inside the function.

182
00:06:59,170 --> 00:07:00,550
Let me just clear this up.

183
00:07:00,670 --> 00:07:02,500
We come inside this function again.

184
00:07:02,500 --> 00:07:04,450
We check if no dot left is truthy.

185
00:07:04,450 --> 00:07:05,530
Yes it's truthy.

186
00:07:05,530 --> 00:07:07,810
So again over here let me just write it over here.

187
00:07:07,810 --> 00:07:10,450
We add Prof with 78.

188
00:07:10,450 --> 00:07:10,900
Right.

189
00:07:10,900 --> 00:07:12,640
So we come again inside the function.

190
00:07:12,640 --> 00:07:14,830
And this does not have anything in the left right.

191
00:07:14,830 --> 00:07:20,680
So over here it this line does not get executed when we call the function with 78.

192
00:07:20,680 --> 00:07:23,320
So we come to the next line which is array dot push node.

193
00:07:23,320 --> 00:07:25,540
So this 78 gets added to the array.

194
00:07:25,540 --> 00:07:28,630
Then we check whether node dot right is truthy.

195
00:07:28,660 --> 00:07:28,840
No.

196
00:07:28,840 --> 00:07:31,690
In the case of 78 it does not have anything in the right as well.

197
00:07:31,690 --> 00:07:31,960
Right.

198
00:07:31,960 --> 00:07:33,040
So it returns.

199
00:07:33,040 --> 00:07:35,260
So this is removed from the call stack.

200
00:07:35,260 --> 00:07:36,430
So 78 is removed.

201
00:07:36,430 --> 00:07:42,130
And at this point when we did the call for 80 we have completed the left right.

202
00:07:42,130 --> 00:07:42,940
So this is done.

203
00:07:42,940 --> 00:07:45,280
Now we do array dot push node with 80.

204
00:07:45,280 --> 00:07:46,870
So we add 80 over here.

205
00:07:46,870 --> 00:07:48,070
So this line is done.

206
00:07:48,070 --> 00:07:49,390
Now we check for the right.

207
00:07:49,390 --> 00:07:52,810
So we go to the right and we see that yes this is also truthy.

208
00:07:52,810 --> 00:07:55,690
So again I'm just writing it in a small manner over here.

209
00:07:55,690 --> 00:07:58,450
So we are calling try with 90 over here in the call stack.

210
00:07:58,450 --> 00:07:58,810
Right.

211
00:07:58,810 --> 00:08:02,500
So again we come over here inside this function.

212
00:08:02,500 --> 00:08:06,310
Now we check for left of 90 which is false.

213
00:08:06,310 --> 00:08:07,870
So this does not get executed.

214
00:08:07,870 --> 00:08:09,580
Then we do array dot push node.

215
00:08:09,580 --> 00:08:10,690
So this node is pushed.

216
00:08:10,690 --> 00:08:12,010
We have 90 over here.

217
00:08:12,010 --> 00:08:13,390
Then we check for the right.

218
00:08:13,390 --> 00:08:14,620
So again that's false.

219
00:08:14,680 --> 00:08:16,450
So this also does not get executed.

220
00:08:16,450 --> 00:08:17,860
And we come out of this call.

221
00:08:17,860 --> 00:08:20,110
So this is done at 90 is done.

222
00:08:20,110 --> 00:08:22,750
So again we are at the call for 80 right.

223
00:08:22,750 --> 00:08:24,610
So for 80 what all is done.

224
00:08:24,610 --> 00:08:26,020
We have completed the left part.

225
00:08:26,020 --> 00:08:29,350
We have completed pushing the node and we have completed the right part.

226
00:08:29,350 --> 00:08:30,580
So we come out of this.

227
00:08:30,580 --> 00:08:32,230
So we come out of the 80 also.

228
00:08:32,230 --> 00:08:34,390
And this is also removed from the call stack.

229
00:08:34,390 --> 00:08:34,900
All right.

230
00:08:34,930 --> 00:08:38,440
Now just the call which is remaining is the 76 call right.

231
00:08:38,440 --> 00:08:40,960
The call on trap function with 76.

232
00:08:40,960 --> 00:08:44,290
So for 76 we have done the left part.

233
00:08:44,290 --> 00:08:48,670
And we also did the array dot push where we were at the current node which was 76.

234
00:08:48,670 --> 00:08:51,790
And now we have just now finished the right part as well.

235
00:08:51,790 --> 00:08:52,930
So this is the right part right.

236
00:08:52,930 --> 00:08:53,950
So that is also done.

237
00:08:53,950 --> 00:08:55,120
So this also returns.

238
00:08:55,120 --> 00:08:57,640
And our call stack is empty at this point.

239
00:08:57,640 --> 00:09:01,690
And we have our output array which is 43 then 50.

240
00:09:01,720 --> 00:09:04,840
Then you have 76 then 7880 and 90.

241
00:09:04,840 --> 00:09:11,290
And notice that the DFS in-order traversal for a binary search tree gives you the array in ascending

242
00:09:11,290 --> 00:09:11,800
order.

243
00:09:12,520 --> 00:09:14,140
And that's what we have over here.

244
00:09:14,140 --> 00:09:21,070
The time complexity of this solution is O of N, which is the same case as the breadth first search

245
00:09:21,070 --> 00:09:25,330
as well, because we're just visiting every node once and doing some constant operation.

246
00:09:25,330 --> 00:09:31,660
But in terms of space complexity, you can see that the space complexity is O of D, where d is the

247
00:09:31,660 --> 00:09:34,540
maximum depth of the binary search tree, right.

248
00:09:34,540 --> 00:09:35,110
In this case.

249
00:09:35,110 --> 00:09:40,420
So this can go up to O of n in the case of the worst case where you have a binary search tree that looks

250
00:09:40,420 --> 00:09:41,500
like a linked list.

251
00:09:41,500 --> 00:09:42,010
All right.

252
00:09:42,040 --> 00:09:45,880
Now over here this is O of log n because this is a balanced binary search tree.

253
00:09:45,880 --> 00:09:48,850
And the depth is O of the depth is log n.

254
00:09:48,850 --> 00:09:49,270
Right.

255
00:09:49,270 --> 00:09:49,720
All right.

256
00:09:49,720 --> 00:09:52,780
So we have seen the DFS in-order traversal.

257
00:09:52,780 --> 00:09:57,040
Now let's look at the others which is preorder and postorder quickly.

258
00:09:57,040 --> 00:09:58,360
So it's the same case right.

259
00:09:58,360 --> 00:10:01,240
So we have just changed the order over here.

260
00:10:01,240 --> 00:10:02,530
So nothing else.

261
00:10:02,530 --> 00:10:05,920
So the time complexity space complexity is the same.

262
00:10:05,920 --> 00:10:07,450
And over here what's happening.

263
00:10:07,450 --> 00:10:10,510
Let's just look at preorder first we start at 76.

264
00:10:10,510 --> 00:10:12,280
We push it to the array right.

265
00:10:12,280 --> 00:10:13,690
And then we go left.

266
00:10:13,690 --> 00:10:14,650
So we go left.

267
00:10:14,650 --> 00:10:17,170
And over here yes it's there.

268
00:10:17,170 --> 00:10:21,460
So at this point we call the uh tree function with 50.

269
00:10:21,460 --> 00:10:23,800
So initially it's called with 76.

270
00:10:23,800 --> 00:10:25,450
So let me just track that.

271
00:10:25,450 --> 00:10:27,610
And now we called it for 50.

272
00:10:28,310 --> 00:10:28,760
All right.

273
00:10:28,790 --> 00:10:31,310
Now, when we come for 50 again we push 50.

274
00:10:31,310 --> 00:10:32,210
So array dot push.

275
00:10:32,210 --> 00:10:35,210
So we push the 50 into our array.

276
00:10:35,210 --> 00:10:38,960
And then we again call it on its left which is 43.

277
00:10:38,960 --> 00:10:41,390
So we have 43 at this point.

278
00:10:41,390 --> 00:10:42,950
Again at this point we are over here.

279
00:10:42,950 --> 00:10:44,420
We push it to our array.

280
00:10:44,420 --> 00:10:45,320
We have 43.

281
00:10:45,320 --> 00:10:52,190
And so at this point we come check its left and its right and there's nothing over there.

282
00:10:52,190 --> 00:10:52,490
Right.

283
00:10:52,490 --> 00:10:54,830
So we are done for this call and this returns.

284
00:10:54,830 --> 00:10:55,850
So this returns.

285
00:10:55,850 --> 00:10:58,550
So now we have the call for 50.

286
00:10:58,550 --> 00:11:04,040
So for the call where we call the drive function for the node 50, we are done with this line where

287
00:11:04,040 --> 00:11:05,930
we pushed 50 and we are done with the left.

288
00:11:05,930 --> 00:11:08,300
Now we check for the right and nothing is there in the right.

289
00:11:08,300 --> 00:11:09,410
So this is also done.

290
00:11:09,410 --> 00:11:10,670
And this returns right.

291
00:11:10,670 --> 00:11:15,410
So now we are in the call where we call the function for 76.

292
00:11:15,410 --> 00:11:19,220
Now in this case the array dot push is done and its left is done.

293
00:11:19,220 --> 00:11:20,540
Now we call its right.

294
00:11:20,540 --> 00:11:23,990
So we again call the try function for 80.

295
00:11:23,990 --> 00:11:26,000
So I'm just writing to 80 over here.

296
00:11:26,000 --> 00:11:28,730
And at this point we push 80 to the array.

297
00:11:28,730 --> 00:11:32,630
Because in this line array dot push node we push the 80 right.

298
00:11:33,170 --> 00:11:35,240
And then we check its left.

299
00:11:35,240 --> 00:11:36,260
So yes it's there.

300
00:11:36,260 --> 00:11:38,600
So we again call T for 78.

301
00:11:38,600 --> 00:11:40,790
And we push it at this line.

302
00:11:40,790 --> 00:11:42,140
We push it right array dot push.

303
00:11:42,140 --> 00:11:45,560
Then we check its left and right which is which is not there.

304
00:11:45,560 --> 00:11:46,100
It's null.

305
00:11:46,100 --> 00:11:47,210
So this returns.

306
00:11:47,210 --> 00:11:50,390
And then we come again to the call for 80.

307
00:11:50,390 --> 00:11:54,830
So for the call of 80 we are done with pushing 80 and we are done with its left.

308
00:11:54,830 --> 00:11:57,050
So now at this part we call its right.

309
00:11:57,050 --> 00:12:00,260
So we go over here again we call try for 90.

310
00:12:00,260 --> 00:12:02,210
And at this point we push 90.

311
00:12:02,240 --> 00:12:04,550
We check its left and right which is not there.

312
00:12:04,550 --> 00:12:07,490
So this returns and this is taken out from the call stack.

313
00:12:07,490 --> 00:12:09,290
And now 80 is also done right.

314
00:12:09,290 --> 00:12:11,720
So 8080 was pushed its left.

315
00:12:11,720 --> 00:12:13,640
We took care of its left and its right.

316
00:12:13,640 --> 00:12:15,380
So at this point this returns right.

317
00:12:15,380 --> 00:12:17,600
So we come back to 76.

318
00:12:17,600 --> 00:12:21,680
Now in this case 76 we already pushed it and its left was taken care.

319
00:12:21,680 --> 00:12:23,720
And its right is also now taken care.

320
00:12:23,720 --> 00:12:26,270
And this is the output that we are getting 76.

321
00:12:26,270 --> 00:12:30,440
Then we get 50, 43, 80, 78 and 90.

322
00:12:30,440 --> 00:12:37,610
So this is the pre order traversal where we go where we push the current first then we go left then

323
00:12:37,610 --> 00:12:38,540
we go right now.

324
00:12:38,540 --> 00:12:41,720
Similarly we you can just check the post order.

325
00:12:41,720 --> 00:12:43,070
Also it will be very much similar.

326
00:12:43,070 --> 00:12:44,690
So you can just try it out on your own.

327
00:12:44,690 --> 00:12:48,140
You can write the call stack like this and try it out on your own.

328
00:12:48,140 --> 00:12:53,090
Now remember the time complexity for these are also O of N, because we are just visiting every node

329
00:12:53,090 --> 00:12:59,780
once and doing some constant time operation, and the space complexity is O of D, where d is the maximum

330
00:12:59,780 --> 00:13:01,700
depth of the binary search tree.