1
00:00:00,540 --> 00:00:01,560
Welcome back.

2
00:00:01,560 --> 00:00:04,260
Let's now code the solutions which we discussed.

3
00:00:04,290 --> 00:00:10,500
Now we will use the same binary search tree which we created or constructed earlier.

4
00:00:10,500 --> 00:00:10,890
All right.

5
00:00:10,890 --> 00:00:15,150
So that we can just write the breadth first and depth first functions.

6
00:00:15,150 --> 00:00:18,960
And then we will call it for the same object the BST object over here.

7
00:00:18,960 --> 00:00:19,590
All right.

8
00:00:19,590 --> 00:00:20,880
So let's get started.

9
00:00:20,880 --> 00:00:24,750
So we are just continuing just to quickly give you a context.

10
00:00:24,750 --> 00:00:26,340
We have the class node over here.

11
00:00:26,340 --> 00:00:28,860
And then we have the class binary search tree.

12
00:00:28,860 --> 00:00:34,140
And over here we have written our previous functions insert and find and remove.

13
00:00:34,140 --> 00:00:35,550
And we continue over here.

14
00:00:35,550 --> 00:00:35,970
All right.

15
00:00:35,970 --> 00:00:38,580
So we have this was a helper method.

16
00:00:38,580 --> 00:00:39,150
Get min.

17
00:00:39,150 --> 00:00:40,410
Now we continue over here.

18
00:00:40,410 --> 00:00:42,870
Let's get started with the breadth first search.

19
00:00:42,870 --> 00:00:45,720
So breadth first let's call it uh breadth first.

20
00:00:46,470 --> 00:00:49,800
And, um, we don't need to pass anything to it.

21
00:00:49,830 --> 00:00:56,190
Now, as we discussed in the, uh, video previously, the approach that we are going to have over here

22
00:00:56,190 --> 00:01:00,480
is we'll have a queue, and then we'll also create an array, which finally we will return.

23
00:01:00,480 --> 00:01:07,920
Now, before we get started, let's just check whether the the binary search tree at this point is empty

24
00:01:07,920 --> 00:01:08,430
or not.

25
00:01:08,430 --> 00:01:11,370
So if this dot root is equal to null.

26
00:01:12,150 --> 00:01:17,430
That means that the binary search tree is empty, and in this case, we just have to return an empty

27
00:01:17,430 --> 00:01:17,850
array.

28
00:01:18,940 --> 00:01:20,440
So that's that.

29
00:01:20,440 --> 00:01:22,660
Now, after this.

30
00:01:22,660 --> 00:01:26,800
Now let's get started with implementing the breadth first search approach, which we discussed.

31
00:01:26,800 --> 00:01:31,780
So let's have let's say a variable array and let this be an empty array.

32
00:01:31,780 --> 00:01:38,290
So we will as we traverse the binary search tree we will push data into this array over here.

33
00:01:38,290 --> 00:01:39,970
And finally we will return this array.

34
00:01:39,970 --> 00:01:40,420
All right.

35
00:01:40,420 --> 00:01:42,970
So again I'm just writing this over here.

36
00:01:42,970 --> 00:01:45,220
At the end we will just return the array.

37
00:01:45,220 --> 00:01:47,050
So that's the approach over here.

38
00:01:47,050 --> 00:01:49,930
And we will also need an empty queue.

39
00:01:49,930 --> 00:01:50,320
All right.

40
00:01:50,320 --> 00:01:54,550
So over here I just mentioning it over here we are to save time.

41
00:01:54,550 --> 00:01:56,830
We are just implementing the queue as an array.

42
00:01:56,830 --> 00:01:58,480
But that's not the best approach.

43
00:01:58,480 --> 00:01:58,900
All right.

44
00:01:58,900 --> 00:02:01,420
So that's just to save time.

45
00:02:01,900 --> 00:02:07,720
Now even in the interview you can say this to the interviewer and go ahead and implement the queue as

46
00:02:07,720 --> 00:02:09,610
an array if the interviewer is okay.

47
00:02:09,610 --> 00:02:13,960
Now to get the best performance, we have to implement the queue as a linked list.

48
00:02:13,990 --> 00:02:16,780
Now we have discussed that in a separate video previously.

49
00:02:16,780 --> 00:02:19,180
Now over here again I'm repeating to save time.

50
00:02:19,180 --> 00:02:23,170
And because that's not the central thing that we are doing over here, the central thing which you're

51
00:02:23,170 --> 00:02:25,450
doing over here is the breadth first traversal approach.

52
00:02:25,450 --> 00:02:25,750
Right.

53
00:02:25,750 --> 00:02:30,700
So because of that, I'm just implementing the queue as a array over here.

54
00:02:30,700 --> 00:02:31,930
So let's write that.

55
00:02:31,930 --> 00:02:34,300
Let let me call the queue as queue itself.

56
00:02:34,300 --> 00:02:36,340
And we're implementing it as an array.

57
00:02:36,760 --> 00:02:37,300
All right.

58
00:02:37,300 --> 00:02:38,800
So we are done with this.

59
00:02:38,800 --> 00:02:42,610
Now to start with what we will do is let's have a variable.

60
00:02:42,610 --> 00:02:43,600
Let's call it node.

61
00:02:43,600 --> 00:02:46,330
And let's initialize this to the root node.

62
00:02:46,990 --> 00:02:47,770
All right.

63
00:02:48,220 --> 00:02:52,450
Now what we will do is we will push this root node into the queue.

64
00:02:52,450 --> 00:02:52,780
All right.

65
00:02:52,780 --> 00:02:55,060
So let's write that queue dot push.

66
00:02:56,200 --> 00:02:58,900
And I'm pushing the node to the queue.

67
00:02:59,740 --> 00:03:05,980
And then we will have a while loop, and we will keep iterating as long as there is something in the

68
00:03:05,980 --> 00:03:06,400
queue.

69
00:03:06,400 --> 00:03:11,470
So if q dot length is greater than zero we keep iterating.

70
00:03:11,470 --> 00:03:15,760
So if q dot length is greater than zero, that means something is there in the queue.

71
00:03:15,910 --> 00:03:21,340
We could also write while q dot length because zero in JavaScript is falsy, right?

72
00:03:21,340 --> 00:03:24,520
So when q dot length becomes zero, that will break out of it.

73
00:03:24,520 --> 00:03:27,910
But I'm just writing it over here as while q dot length greater than zero.

74
00:03:27,910 --> 00:03:29,470
So both approaches are correct.

75
00:03:29,500 --> 00:03:38,800
Now what we will do is first we will take the last the first in again remember Q is a Fifo data structure

76
00:03:38,800 --> 00:03:39,250
right.

77
00:03:39,250 --> 00:03:41,560
So that's why we are using a queue over here.

78
00:03:41,650 --> 00:03:45,910
So we need to take out what came in first right.

79
00:03:45,910 --> 00:03:48,250
So that would be at the beginning of the array.

80
00:03:48,280 --> 00:03:52,930
Now again I'm repeating we are implementing it as an array over here to save time.

81
00:03:52,930 --> 00:03:57,880
But if you are taking something out from the beginning of the array, we know that that's an O of N

82
00:03:57,880 --> 00:03:58,420
operation.

83
00:03:58,420 --> 00:04:00,970
So that's why it's not advised to do it in that manner.

84
00:04:00,970 --> 00:04:03,580
But again, because that's not the central thing over here.

85
00:04:03,580 --> 00:04:04,960
It's fine to do it like this.

86
00:04:04,960 --> 00:04:08,380
So we will take out the first element from the Q array.

87
00:04:08,380 --> 00:04:12,490
So for this let's say node is equal to q dot shift.

88
00:04:13,550 --> 00:04:16,820
And shift takes the first element from the queue, right?

89
00:04:16,820 --> 00:04:18,710
So we have taken out the first element.

90
00:04:18,710 --> 00:04:21,530
Now what we will do is we will push this into the array.

91
00:04:21,530 --> 00:04:22,730
So array dot push.

92
00:04:23,520 --> 00:04:29,970
Node, we will push it into the array, and then we will check if there is something on the left of

93
00:04:29,970 --> 00:04:35,010
the node or on the right of the node, and if it's there, we will put those elements into the queue.

94
00:04:35,010 --> 00:04:36,120
So let's do that.

95
00:04:36,120 --> 00:04:42,960
So if node dot left that means if there is something in on the left of the node then we will push it

96
00:04:42,960 --> 00:04:43,470
to the queue.

97
00:04:43,470 --> 00:04:44,790
So q dot push.

98
00:04:45,580 --> 00:04:46,810
No dot left.

99
00:04:48,380 --> 00:04:48,980
All right.

100
00:04:48,980 --> 00:04:49,520
Again.

101
00:04:49,520 --> 00:04:51,860
After this, we will check if something is there on the right.

102
00:04:51,860 --> 00:04:53,480
So if no dot right.

103
00:04:53,480 --> 00:04:55,610
If it's there we'll just push it to the q.

104
00:04:55,610 --> 00:04:58,100
So q dot push no dot.

105
00:04:58,100 --> 00:04:58,670
Right.

106
00:05:02,130 --> 00:05:02,670
All right.

107
00:05:02,670 --> 00:05:04,020
And we are almost done.

108
00:05:04,020 --> 00:05:07,710
So again, we will come to this part over here.

109
00:05:07,710 --> 00:05:11,610
And then because we have pushed something to the queue, if there is something in the queue, it will

110
00:05:11,610 --> 00:05:12,540
keep iterating.

111
00:05:12,540 --> 00:05:16,440
Now once we are done and there is nothing more in the queue, we will come out.

112
00:05:16,440 --> 00:05:20,820
And at this point we just need to return this array which we have created over here.

113
00:05:20,820 --> 00:05:21,450
All right.

114
00:05:21,450 --> 00:05:25,590
So that's the end of our breadth first traversal method over here.

115
00:05:26,010 --> 00:05:30,960
Now we have already created we have written the code to create this binary search tree.

116
00:05:30,960 --> 00:05:33,840
So again I have these insert calls over here.

117
00:05:33,840 --> 00:05:34,980
So let's run that.

118
00:05:34,980 --> 00:05:39,960
And after that we will just call the breadth first method which you have uh written over here.

119
00:05:39,960 --> 00:05:41,700
And what is the expectation.

120
00:05:41,700 --> 00:05:44,040
Let's just write the expectation also over here.

121
00:05:44,040 --> 00:05:46,890
Now again I'm writing it as a comment.

122
00:05:47,740 --> 00:05:49,630
So breadth first search.

123
00:05:49,630 --> 00:05:52,360
The output should be over here.

124
00:05:52,360 --> 00:05:53,920
We should get 20 right?

125
00:05:53,920 --> 00:05:55,630
Then we should get 635.

126
00:05:55,630 --> 00:05:59,920
So let's write that 20 comma six comma 35.

127
00:05:59,920 --> 00:06:03,700
And then over here we should get three eight 2755.

128
00:06:03,700 --> 00:06:03,910
Right.

129
00:06:03,910 --> 00:06:08,350
So three eight 2755.

130
00:06:08,350 --> 00:06:10,360
And after that we should get these elements.

131
00:06:10,360 --> 00:06:11,860
That is one three.

132
00:06:12,680 --> 00:06:15,890
25, 29 and 60.

133
00:06:16,130 --> 00:06:17,540
That's the expectation.

134
00:06:17,540 --> 00:06:18,560
So let's go ahead.

135
00:06:18,560 --> 00:06:26,570
And after we do creating, after we create this binary search tree we will call BST dot pred first.

136
00:06:26,570 --> 00:06:29,000
All right so BST dot.

137
00:06:29,850 --> 00:06:30,840
Breakfast.

138
00:06:31,390 --> 00:06:34,600
And this is the expectation which we have over here.

139
00:06:34,600 --> 00:06:37,420
Now let's run our code and see whether it's working.

140
00:06:37,990 --> 00:06:38,440
All right.

141
00:06:38,440 --> 00:06:39,730
So we have run the code.

142
00:06:40,710 --> 00:06:42,780
And we are inserting nodes to the array.

143
00:06:42,780 --> 00:06:46,500
So that's why we have an array of 12 nodes over here.

144
00:06:46,650 --> 00:06:47,280
Right.

145
00:06:47,280 --> 00:06:50,040
So let's again uh just check it.

146
00:06:50,040 --> 00:06:52,380
So this is the output that we are getting.

147
00:06:52,380 --> 00:06:54,480
Now we have 20 which is correct.

148
00:06:54,480 --> 00:07:03,810
Then we have the node with value 630 538 2750 513 2529 and 60, which is correct.

149
00:07:03,810 --> 00:07:06,540
So yes, our breadth first search is working.

150
00:07:06,540 --> 00:07:07,020
Again.

151
00:07:07,020 --> 00:07:12,600
We will look at this code in the walkthrough section and analyze its complexity again.

152
00:07:12,600 --> 00:07:12,960
All right.

153
00:07:12,960 --> 00:07:15,660
Just to be very clear with what is happening over here.

154
00:07:15,660 --> 00:07:21,390
Now let's go ahead and implement the depth first methods which we discussed in the previous video.

155
00:07:21,390 --> 00:07:23,670
So let me make some placeholders over here.

156
00:07:23,670 --> 00:07:25,170
Let's call it DFS.

157
00:07:25,410 --> 00:07:27,990
And we have to write three functions.

158
00:07:27,990 --> 00:07:29,520
The first one is in order.

159
00:07:31,290 --> 00:07:32,010
All right.

160
00:07:32,010 --> 00:07:35,760
And the second one is DFS preorder.

161
00:07:40,370 --> 00:07:42,530
And the last one is DFS.

162
00:07:42,530 --> 00:07:43,310
Post order.

163
00:07:48,510 --> 00:07:49,140
All right.

164
00:07:49,140 --> 00:07:50,340
Now let's go ahead.

165
00:07:50,340 --> 00:07:53,010
Now we start with in order again.

166
00:07:53,010 --> 00:07:57,180
We start with checking whether the, uh, binary search tree is empty.

167
00:07:57,210 --> 00:07:59,280
If it's empty, we will just return an empty array.

168
00:07:59,280 --> 00:08:04,380
So to take care of that edge case, let's write if this dot root.

169
00:08:05,620 --> 00:08:09,910
Is equal to null, then we will just return an empty array.

170
00:08:11,350 --> 00:08:12,040
All right.

171
00:08:13,080 --> 00:08:13,650
Oops.

172
00:08:13,950 --> 00:08:18,000
Okay, so if that is not the case, then we proceed further.

173
00:08:18,000 --> 00:08:18,960
So what do we do.

174
00:08:18,960 --> 00:08:21,990
We need to have an array which will be the output right.

175
00:08:21,990 --> 00:08:23,790
Which is what we will return.

176
00:08:23,790 --> 00:08:25,020
So let's say const array.

177
00:08:25,020 --> 00:08:26,040
It's an empty array.

178
00:08:26,040 --> 00:08:27,810
Finally we will return this array.

179
00:08:28,750 --> 00:08:32,860
Now we will need to traverse the binary search tree and push elements to this array.

180
00:08:32,860 --> 00:08:34,270
So that's what we are going to do.

181
00:08:34,300 --> 00:08:36,880
Now let's start with the root node.

182
00:08:36,880 --> 00:08:39,070
Let's say current is equal to this dot root.

183
00:08:41,220 --> 00:08:43,710
And we will write a function, right?

184
00:08:43,710 --> 00:08:46,560
Let's write a function which will traverse the array.

185
00:08:46,560 --> 00:08:47,880
So let's call it Trav.

186
00:08:47,880 --> 00:08:50,640
And for this function we will be passing the node.

187
00:08:50,640 --> 00:08:53,010
In this case that's the node root node.

188
00:08:53,010 --> 00:08:56,760
And then over here we will call the function which is Trav.

189
00:08:56,790 --> 00:08:57,060
All right.

190
00:08:57,060 --> 00:09:00,360
So we will call it with the current node which is the root node.

191
00:09:00,360 --> 00:09:02,940
At this point this is how it's going to work.

192
00:09:02,940 --> 00:09:06,000
Now over here is where the recursive calls will happen.

193
00:09:06,000 --> 00:09:06,180
Right.

194
00:09:06,180 --> 00:09:10,020
So we are writing this as a function so that we can recursively call this function.

195
00:09:10,020 --> 00:09:13,590
We could also write it outside but it's convenient to write it over here.

196
00:09:13,590 --> 00:09:16,140
Now what is it that we have to do.

197
00:09:16,140 --> 00:09:17,850
Remember inorder traversal.

198
00:09:17,850 --> 00:09:21,030
Let's just quickly revise what we have seen before.

199
00:09:21,030 --> 00:09:25,470
Let's say I have I'm just making some space over here.

200
00:09:26,730 --> 00:09:28,800
Now if I have a node.

201
00:09:30,250 --> 00:09:31,870
Let's say that's two.

202
00:09:32,200 --> 00:09:37,930
And on its left I have one, and on its right I have three, right?

203
00:09:38,350 --> 00:09:46,090
So if this is the case, if we are traversing this tree in order, that means first we have to go to

204
00:09:46,090 --> 00:09:49,630
the left node, then the current node and then the right node right.

205
00:09:49,630 --> 00:09:51,190
So that's the importance right.

206
00:09:51,190 --> 00:09:56,080
So that will be the only difference between these three functions that we are writing over here now

207
00:09:56,200 --> 00:09:58,360
for depth first inorder traversal.

208
00:09:58,360 --> 00:09:59,650
First we go to the left.

209
00:09:59,650 --> 00:10:03,100
Then we push the current node to the array.

210
00:10:03,100 --> 00:10:04,270
And then we go to the right.

211
00:10:04,270 --> 00:10:05,110
So let's do that.

212
00:10:05,110 --> 00:10:08,710
So let's check whether there is a left node for the current node.

213
00:10:08,710 --> 00:10:15,130
So if node dot left that means if there is a left node then we have to recursively call the function

214
00:10:15,130 --> 00:10:16,420
for that particular node.

215
00:10:16,420 --> 00:10:18,010
So trave node dot left.

216
00:10:20,200 --> 00:10:20,980
All right.

217
00:10:20,980 --> 00:10:26,440
Now, after this, after we are done with the left, we push the value in the current node to the array.

218
00:10:26,440 --> 00:10:28,750
So over here we do array dot push.

219
00:10:30,130 --> 00:10:32,200
And then that's the node right.

220
00:10:32,200 --> 00:10:33,610
So that's node over here.

221
00:10:34,670 --> 00:10:36,110
And then we check for the right.

222
00:10:36,110 --> 00:10:36,290
Right.

223
00:10:36,290 --> 00:10:37,430
So we are done with the left.

224
00:10:37,430 --> 00:10:40,580
We are done with pushing the value of the current node to the array.

225
00:10:40,610 --> 00:10:42,350
Now we traverse the right side.

226
00:10:42,350 --> 00:10:44,690
So if there is a node on the right.

227
00:10:44,690 --> 00:10:46,250
So if node dot right.

228
00:10:47,000 --> 00:10:47,720
What do we do?

229
00:10:47,720 --> 00:10:50,810
We recursively call the trough function for that particular node.

230
00:10:50,810 --> 00:10:52,370
So node dot right.

231
00:10:52,940 --> 00:10:57,950
And that brings us to the end of our breadth depth first in order function.

232
00:10:57,950 --> 00:10:58,400
All right.

233
00:10:58,400 --> 00:11:01,160
So let's quickly write these other two also.

234
00:11:01,160 --> 00:11:03,350
And then we will just test them together.

235
00:11:03,350 --> 00:11:09,020
Now again I'm just going to take the same code over from here because it's going to be almost the same

236
00:11:09,020 --> 00:11:10,910
thing pasting it over here.

237
00:11:11,630 --> 00:11:13,520
And let me paste it over here as well.

238
00:11:13,520 --> 00:11:15,260
Now for pre-order.

239
00:11:15,260 --> 00:11:18,650
Remember the order to be followed is for preorder.

240
00:11:18,650 --> 00:11:19,160
It's.

241
00:11:20,550 --> 00:11:23,010
Current and then left.

242
00:11:23,780 --> 00:11:24,440
And then.

243
00:11:24,440 --> 00:11:25,040
Right.

244
00:11:25,130 --> 00:11:25,760
Right.

245
00:11:25,760 --> 00:11:29,330
And for post order, it's left, right and then current.

246
00:11:31,190 --> 00:11:34,910
It's left, then right, then current.

247
00:11:35,030 --> 00:11:37,400
Now again, just for remembering.

248
00:11:37,400 --> 00:11:39,860
Notice that left and right are always together.

249
00:11:39,860 --> 00:11:40,100
Right?

250
00:11:40,100 --> 00:11:43,880
You have left and right over here and left and right over here in these two cases.

251
00:11:43,880 --> 00:11:47,810
And when you have three you have to put current as the first.

252
00:11:47,810 --> 00:11:48,170
Right.

253
00:11:48,170 --> 00:11:49,430
So pre means before.

254
00:11:49,430 --> 00:11:51,170
So you can just remember it in that manner.

255
00:11:51,170 --> 00:11:52,250
So you put current first.

256
00:11:52,250 --> 00:11:54,350
And when you have post you put current last.

257
00:11:54,350 --> 00:11:54,860
All right.

258
00:11:54,860 --> 00:11:58,520
So again that's the only difference that we are that we need to make over here.

259
00:11:58,520 --> 00:12:01,610
So for pre order we have to shift this to the first part.

260
00:12:01,610 --> 00:12:06,680
So first we push the current node value into the array.

261
00:12:06,680 --> 00:12:08,750
And then we traverse the left side.

262
00:12:08,750 --> 00:12:10,190
And then we traverse the right side.

263
00:12:10,190 --> 00:12:10,850
So that's it.

264
00:12:10,850 --> 00:12:15,200
Now for post order we have to traverse left first then right.

265
00:12:15,200 --> 00:12:20,810
And after we are done with both of these then we will push the value of the current node into the array.

266
00:12:20,810 --> 00:12:25,970
So that's the only difference between these three depth first search methods.

267
00:12:25,970 --> 00:12:26,420
All right.

268
00:12:26,420 --> 00:12:27,140
So we are done.

269
00:12:27,140 --> 00:12:29,540
We have returned all the three functions over here.

270
00:12:29,540 --> 00:12:33,110
Now let's go ahead and call the function.

271
00:12:33,110 --> 00:12:34,280
So let's have.

272
00:12:34,860 --> 00:12:35,280
Probably.

273
00:12:35,280 --> 00:12:36,660
We'll just do it one by one.

274
00:12:36,660 --> 00:12:39,180
Now we have our array.

275
00:12:39,330 --> 00:12:41,280
We have our binary search tree over here.

276
00:12:41,280 --> 00:12:42,990
Now let's see what we get.

277
00:12:42,990 --> 00:12:44,760
So let's go ahead and run the code.

278
00:12:45,440 --> 00:12:50,630
And again, I'm going to amend this because we are already done with the breadth first part, but we

279
00:12:50,630 --> 00:12:53,780
are only going to check or test the depth first part over here.

280
00:12:53,780 --> 00:12:54,290
All right.

281
00:12:54,290 --> 00:12:56,600
So we have created this binary search tree.

282
00:12:56,600 --> 00:13:00,110
Now let's call the depth first functions that we have written.

283
00:13:00,110 --> 00:13:01,850
So BST dot.

284
00:13:02,690 --> 00:13:03,380
DFS.

285
00:13:03,380 --> 00:13:05,000
Let's start with in order.

286
00:13:06,000 --> 00:13:06,330
All right.

287
00:13:06,330 --> 00:13:07,050
So.

288
00:13:08,390 --> 00:13:09,020
Again.

289
00:13:09,020 --> 00:13:10,730
Yeah, it just says that it's there.

290
00:13:10,730 --> 00:13:13,040
I should have put the brackets.

291
00:13:13,070 --> 00:13:15,200
All right, let's put the brackets.

292
00:13:15,500 --> 00:13:18,260
Now we get 12 nodes over here.

293
00:13:18,260 --> 00:13:24,950
Now again remember when we do in-order traversal on a binary search tree we will get the nodes.

294
00:13:24,950 --> 00:13:26,990
The values of the nodes will be in ascending order.

295
00:13:26,990 --> 00:13:28,460
So it's very easy to check.

296
00:13:28,460 --> 00:13:30,890
So let's just check whether this is in ascending order.

297
00:13:30,890 --> 00:13:36,770
So we have 13368, 20, 25, 27, 29, 35, 55 and 60.

298
00:13:36,770 --> 00:13:38,330
So yes, this is in ascending order.

299
00:13:38,330 --> 00:13:44,330
So we have the uh the DFS inorder traversal is working again just to quickly revise what's happening

300
00:13:44,330 --> 00:13:44,930
over here.

301
00:13:44,930 --> 00:13:46,520
We go to the left first right.

302
00:13:46,520 --> 00:13:47,690
So we start at 20.

303
00:13:47,720 --> 00:13:48,950
We go to its left.

304
00:13:48,950 --> 00:13:51,680
We go to the left of six and we come to three.

305
00:13:51,680 --> 00:13:54,620
We go to its left which is three, and there's nothing in its left.

306
00:13:54,620 --> 00:13:54,980
Right.

307
00:13:54,980 --> 00:13:57,140
So this becomes current and we push one.

308
00:13:57,140 --> 00:13:58,370
So that's how we get one.

309
00:13:58,370 --> 00:14:00,830
And then we go to its right which again is nothing.

310
00:14:00,830 --> 00:14:01,940
So we come back.

311
00:14:01,940 --> 00:14:03,860
So the left of this is done.

312
00:14:03,860 --> 00:14:05,120
So this is now current right.

313
00:14:05,120 --> 00:14:06,110
So we push this three.

314
00:14:06,110 --> 00:14:07,280
That's this three over here.

315
00:14:07,280 --> 00:14:09,980
Then we go to its right which is this three over here.

316
00:14:09,980 --> 00:14:16,010
And then uh so this part is over this and this is over which is the left of this right left of the node

317
00:14:16,010 --> 00:14:16,730
with value six.

318
00:14:16,730 --> 00:14:19,010
Then we push the current node which is six.

319
00:14:19,010 --> 00:14:21,830
We go to its right which is eight, and so on and so forth.

320
00:14:21,830 --> 00:14:26,060
So that's how the breadth the depth first search in order works.

321
00:14:26,060 --> 00:14:26,300
Right.

322
00:14:26,300 --> 00:14:27,320
So we are done with that.

323
00:14:27,320 --> 00:14:29,360
Now let's go ahead and check.

324
00:14:30,110 --> 00:14:31,520
Depth first search.

325
00:14:31,550 --> 00:14:33,050
Pre order and post order.

326
00:14:33,050 --> 00:14:38,030
So we have DFS uh BST which is the binary search tree dot depth.

327
00:14:38,030 --> 00:14:38,690
First.

328
00:14:39,200 --> 00:14:40,370
Uh let's do it.

329
00:14:40,370 --> 00:14:41,810
Um pre order first.

330
00:14:42,500 --> 00:14:43,130
Okay.

331
00:14:45,690 --> 00:14:46,080
All right.

332
00:14:46,080 --> 00:14:48,660
So when we do this we are getting 12 nodes.

333
00:14:48,690 --> 00:14:50,880
Again remember preorder is that what's the order.

334
00:14:50,880 --> 00:14:52,200
We have written the order over here.

335
00:14:52,200 --> 00:14:53,790
We need to put current first.

336
00:14:53,790 --> 00:14:56,610
Pre means current is first current left and right.

337
00:14:56,610 --> 00:14:57,750
So that's pre order right.

338
00:14:57,750 --> 00:14:59,820
So we are starting at the node.

339
00:14:59,820 --> 00:15:05,100
So you can see that the first node is 20 itself because that's the current and current is pushed to

340
00:15:05,100 --> 00:15:05,730
the array.

341
00:15:05,850 --> 00:15:08,520
Then after that we move to the left right.

342
00:15:08,520 --> 00:15:09,570
So we come to six.

343
00:15:09,570 --> 00:15:10,440
We push it in.

344
00:15:10,440 --> 00:15:12,090
So we have six over here right.

345
00:15:12,090 --> 00:15:13,290
So that's pushed.

346
00:15:13,290 --> 00:15:15,570
And then we go to its left which is three.

347
00:15:15,570 --> 00:15:19,470
And three is pushed because that is the current node at this point.

348
00:15:19,470 --> 00:15:22,650
And then we go to its left which is one, and we push one.

349
00:15:22,650 --> 00:15:24,750
And there's nothing more to go to its left.

350
00:15:24,750 --> 00:15:26,610
So again we try right.

351
00:15:26,610 --> 00:15:27,780
There's nothing in the right.

352
00:15:27,780 --> 00:15:29,340
So we come back to here.

353
00:15:29,340 --> 00:15:31,680
So we have done with current and we are done with left.

354
00:15:31,680 --> 00:15:32,880
And then we go with right.

355
00:15:32,880 --> 00:15:34,440
So that's this three over here.

356
00:15:34,440 --> 00:15:38,220
So at this point we are done with current and the left of six.

357
00:15:38,220 --> 00:15:40,500
So we go to the right of six which gives us eight.

358
00:15:40,500 --> 00:15:41,550
And it goes on like that.

359
00:15:41,550 --> 00:15:43,500
So that is pre order DFS.

360
00:15:43,500 --> 00:15:44,070
All right.

361
00:15:44,070 --> 00:15:49,380
Now again let's go ahead and try uh DFS post order.

362
00:15:53,690 --> 00:15:54,080
All right.

363
00:15:54,080 --> 00:15:57,710
So over here post order means we have to do left then right.

364
00:15:57,710 --> 00:16:00,710
And then we come to the current node and push its value to the array.

365
00:16:00,710 --> 00:16:02,510
So that's post order DFS.

366
00:16:02,510 --> 00:16:03,320
So let's check.

367
00:16:03,320 --> 00:16:04,580
So we start at 20.

368
00:16:04,610 --> 00:16:06,380
We first have to go left right.

369
00:16:06,380 --> 00:16:07,640
So we go left again.

370
00:16:07,640 --> 00:16:09,140
We go left again we go left.

371
00:16:09,140 --> 00:16:10,100
We reach over here.

372
00:16:10,100 --> 00:16:11,810
There's nothing more to go left right.

373
00:16:11,810 --> 00:16:14,510
So over here um we are done with left.

374
00:16:14,510 --> 00:16:16,040
And we try right.

375
00:16:16,040 --> 00:16:16,640
There is nothing.

376
00:16:16,640 --> 00:16:17,000
Right.

377
00:16:17,000 --> 00:16:20,420
So then we put the we push the current value, which is one at this point.

378
00:16:20,420 --> 00:16:21,710
And one comes over here.

379
00:16:21,710 --> 00:16:22,160
All right.

380
00:16:22,160 --> 00:16:23,870
So after this we are done with this.

381
00:16:23,870 --> 00:16:26,510
Now we come over here we did left.

382
00:16:26,510 --> 00:16:27,380
Then we go right.

383
00:16:27,380 --> 00:16:29,000
So this three is pushed over here.

384
00:16:29,000 --> 00:16:29,480
Right.

385
00:16:29,480 --> 00:16:30,380
Then we are back.

386
00:16:30,380 --> 00:16:32,090
So left and right are then done.

387
00:16:32,090 --> 00:16:34,640
So then this three is pushed over here to the array.

388
00:16:34,640 --> 00:16:35,990
So that's this three over here.

389
00:16:35,990 --> 00:16:37,310
So we are done with this part.

390
00:16:37,310 --> 00:16:39,440
So this is the left of six right.

391
00:16:39,440 --> 00:16:42,020
So after that we have to do the right of six which is eight.

392
00:16:42,020 --> 00:16:43,610
So that's why you have eight over here.

393
00:16:43,610 --> 00:16:45,470
Then left and right of six is done.

394
00:16:45,470 --> 00:16:47,510
And then we push the current value which is six.

395
00:16:47,510 --> 00:16:48,860
So you get six over here.

396
00:16:48,860 --> 00:16:51,740
And at this point the left of 20 is done.

397
00:16:51,740 --> 00:16:53,840
Then we start with the right of 20 right.

398
00:16:53,840 --> 00:16:55,520
So we come over here again.

399
00:16:55,520 --> 00:16:56,390
We go to the left.

400
00:16:56,390 --> 00:16:57,140
We go to the left.

401
00:16:57,140 --> 00:16:59,390
And that's how we push 25 to the array.

402
00:16:59,390 --> 00:17:00,680
And it goes on like that.

403
00:17:00,680 --> 00:17:02,840
So yes, our code is working.

404
00:17:02,840 --> 00:17:08,720
We have successfully coded the breadth first search approach and the three methods for depth first search,

405
00:17:08,720 --> 00:17:11,330
which is in-order pre-order and post order.

406
00:17:11,330 --> 00:17:16,670
Now let's take a quick sample, uh, um, binary search tree and walk through the code.

407
00:17:16,670 --> 00:17:20,480
Because again, remember in the interview you will have to walk through the code once you have written

408
00:17:20,480 --> 00:17:20,660
it.

409
00:17:20,660 --> 00:17:25,730
And we will quickly relook at the complexity analysis of these methods that we have written.