1
00:00:00,670 --> 00:00:01,630
Hi everyone.

2
00:00:01,630 --> 00:00:03,190
Let's do this question.

3
00:00:03,190 --> 00:00:07,330
Design a binary search tree class that supports the following.

4
00:00:07,330 --> 00:00:08,500
Insert a value.

5
00:00:08,500 --> 00:00:09,580
Remove a value.

6
00:00:09,580 --> 00:00:13,960
This method should remove the first occurrence of a value and then find a value.

7
00:00:13,960 --> 00:00:17,470
If the value is found, it should return the node with the value.

8
00:00:17,470 --> 00:00:18,760
Else return false.

9
00:00:18,760 --> 00:00:24,790
Now, because this is a standard question, let's directly dive in and see how we can solve this question.

10
00:00:24,790 --> 00:00:27,370
So we have to design a binary search tree.

11
00:00:27,370 --> 00:00:30,070
And these are the three functions that we should write.

12
00:00:30,280 --> 00:00:33,190
All right so insert remove and find.

13
00:00:33,190 --> 00:00:35,230
So these are the three functions that we should write.

14
00:00:35,260 --> 00:00:37,630
Now let's get started with the insert function.

15
00:00:37,630 --> 00:00:41,620
Now for this let me just take a sample binary search tree over here.

16
00:00:41,620 --> 00:00:45,400
Now again when the initially the binary search tree is empty.

17
00:00:45,400 --> 00:00:47,350
And let's say we insert 20.

18
00:00:47,350 --> 00:00:50,290
So at that point we have to set 20 as the root node.

19
00:00:50,290 --> 00:00:50,740
All right.

20
00:00:50,770 --> 00:00:56,650
Now after that let's say all these nodes are already inserted so that we take a generic case and we

21
00:00:56,650 --> 00:00:58,840
can understand how the insert function works.

22
00:00:58,840 --> 00:01:01,150
So over here we have a binary search tree.

23
00:01:01,150 --> 00:01:06,550
You can notice that every element or every node to the left of 20 is less than 20.

24
00:01:06,550 --> 00:01:09,580
And every node to the right of 20 is greater than 20.

25
00:01:09,580 --> 00:01:09,880
Right.

26
00:01:09,880 --> 00:01:12,310
So that's the binary search tree property.

27
00:01:12,340 --> 00:01:16,270
Now let's say we want to insert a node with value 29.

28
00:01:16,270 --> 00:01:17,410
So what do we do.

29
00:01:17,410 --> 00:01:20,590
So over here we start always at the root.

30
00:01:20,590 --> 00:01:20,950
All right.

31
00:01:20,950 --> 00:01:22,150
So we start at the root.

32
00:01:22,150 --> 00:01:23,650
So we start at 20.

33
00:01:23,650 --> 00:01:27,790
And we compare the value at this node with the value to be inserted.

34
00:01:27,790 --> 00:01:32,470
So we see that 29 which is the value to be inserted is greater than 20.

35
00:01:32,470 --> 00:01:32,830
Right.

36
00:01:32,830 --> 00:01:35,860
So in this case what we do is we move to the right.

37
00:01:35,860 --> 00:01:38,590
So we move to the right in the binary search tree.

38
00:01:38,590 --> 00:01:44,740
Now we check whether over here is there a node or is it null if over here there was nothing and if there

39
00:01:44,740 --> 00:01:48,010
was just null over here, we could have just inserted 29 over here.

40
00:01:48,010 --> 00:01:51,460
But now we see that there is another node over here which is 35.

41
00:01:51,460 --> 00:01:56,020
So we compare the value of this node and the value of the node to be inserted.

42
00:01:56,020 --> 00:01:59,590
So we see that 29 is less than 35.

43
00:01:59,590 --> 00:01:59,920
Right.

44
00:01:59,920 --> 00:02:03,010
So because it's less we move in the left direction.

45
00:02:03,010 --> 00:02:08,200
So again we move over here and we check whether over here is there a node or is it null.

46
00:02:08,200 --> 00:02:11,410
So if it was null over here we would have inserted 29 over here.

47
00:02:11,410 --> 00:02:13,120
But we see that there is a node over here.

48
00:02:13,120 --> 00:02:15,550
So we compare 27 and 29.

49
00:02:15,550 --> 00:02:18,670
And we see that 29 is greater than 27.

50
00:02:18,670 --> 00:02:20,950
So we move in the right direction.

51
00:02:20,950 --> 00:02:23,380
But over here we can see that there is nothing over here.

52
00:02:23,380 --> 00:02:23,620
Right.

53
00:02:23,620 --> 00:02:26,770
So the right node to 27 over here is null.

54
00:02:26,770 --> 00:02:29,170
So we can just insert 29 over here.

55
00:02:29,170 --> 00:02:31,960
And that's how the insert function will work.

56
00:02:31,960 --> 00:02:32,170
Right.

57
00:02:32,170 --> 00:02:33,580
So it's pretty straightforward.

58
00:02:33,580 --> 00:02:36,340
We just need to be aware how to traverse the tree.

59
00:02:36,340 --> 00:02:42,070
So if we find a value if we see that this value over here is less than 29 for example, what we saw

60
00:02:42,070 --> 00:02:44,500
over here, we move in the right direction, right.

61
00:02:44,500 --> 00:02:47,770
So over here we have something which is greater than 2920 right.

62
00:02:47,770 --> 00:02:49,360
So we move in the right direction.

63
00:02:49,360 --> 00:02:53,080
And over here again we saw that 29 is less than 35.

64
00:02:53,080 --> 00:02:54,640
So we move in the left direction.

65
00:02:54,640 --> 00:02:55,270
So that's it.

66
00:02:55,270 --> 00:02:59,230
And then we do this till we reach a place where nothing is there.

67
00:02:59,230 --> 00:03:01,990
And then we insert 29 in the correct place.

68
00:03:01,990 --> 00:03:02,470
All right.

69
00:03:02,470 --> 00:03:04,330
So that's how the insert function works.

70
00:03:04,330 --> 00:03:07,240
Now let's look at the find function which we have to write.

71
00:03:07,240 --> 00:03:08,980
And again it's also similar.

72
00:03:08,980 --> 00:03:13,180
We just need to traverse the tree and look at the correct position right.

73
00:03:13,180 --> 00:03:18,310
For example let's say we want to see whether there is a node with value eight.

74
00:03:18,310 --> 00:03:21,610
So again we start at the root node which is 20.

75
00:03:21,610 --> 00:03:24,100
And we compare 20 with the value eight.

76
00:03:24,100 --> 00:03:26,350
And we see that eight is less than 20.

77
00:03:26,350 --> 00:03:32,350
And we know that any node which has a value less than 20 has to be part of the left subtree.

78
00:03:32,350 --> 00:03:32,680
Right.

79
00:03:32,680 --> 00:03:37,510
So we started the node and as eight is less than 20 we move in the left direction.

80
00:03:37,510 --> 00:03:42,370
Now we have six over here again we compare six and 20.

81
00:03:42,370 --> 00:03:46,090
And we see that six is less than eight right.

82
00:03:46,240 --> 00:03:48,310
Again not six and 26 and eight right.

83
00:03:48,310 --> 00:03:50,200
So eight is the value that we are trying to find.

84
00:03:50,200 --> 00:03:53,110
So we see that six is less than eight right.

85
00:03:53,110 --> 00:03:57,160
So eight which is greater than six has to be on the right side of six.

86
00:03:57,160 --> 00:03:57,460
Right.

87
00:03:57,460 --> 00:04:00,760
Because anything greater than six has to be on its right side.

88
00:04:00,760 --> 00:04:05,710
So we move in the right direction and over there again we come to eight and we see that yes eight is

89
00:04:05,710 --> 00:04:06,340
equal to eight.

90
00:04:06,340 --> 00:04:07,780
So we have found the node.

91
00:04:07,780 --> 00:04:11,410
Now let's say there was uh another node over here.

92
00:04:11,410 --> 00:04:14,890
Let's say for example we are trying to find the node with value nine.

93
00:04:14,890 --> 00:04:17,230
Again we would have taken the same direction.

94
00:04:17,230 --> 00:04:18,550
We would have started at 20.

95
00:04:18,550 --> 00:04:19,990
And then we come to six.

96
00:04:19,990 --> 00:04:22,510
Then we move in the right direction and we come to eight.

97
00:04:22,510 --> 00:04:28,720
And then because we want to find the node with value nine, it has to be there on the right side of

98
00:04:28,720 --> 00:04:29,890
eight, if at all it is there.

99
00:04:29,890 --> 00:04:30,130
Right.

100
00:04:30,130 --> 00:04:32,050
So we check is there anything over here.

101
00:04:32,050 --> 00:04:33,730
And let's say we see there is nothing.

102
00:04:33,730 --> 00:04:34,480
It's null right.

103
00:04:34,480 --> 00:04:39,760
So at this point we can be sure that there is no value nine in this binary search tree.

104
00:04:39,760 --> 00:04:40,210
All right.

105
00:04:40,210 --> 00:04:42,040
So that's how the find function works.

106
00:04:42,040 --> 00:04:44,920
So we have seen the insert function and the find function.

107
00:04:44,920 --> 00:04:47,650
Now let's proceed and look at the remove function.

108
00:04:47,650 --> 00:04:50,110
So these two are very straightforward.

109
00:04:50,110 --> 00:04:51,610
The insert and find function.

110
00:04:51,610 --> 00:04:56,350
Now in the remove function let's see the different cases which are possible.

111
00:04:56,350 --> 00:04:59,020
Again we have our simple binary search tree over here.

112
00:04:59,020 --> 00:05:00,070
Now the no.

113
00:05:00,430 --> 00:05:02,140
Which is to be deleted, right?

114
00:05:02,140 --> 00:05:05,230
Can be of three possible types one.

115
00:05:05,230 --> 00:05:06,490
It could be a leaf node.

116
00:05:06,520 --> 00:05:09,610
Second, it could be a node which has only one child.

117
00:05:09,610 --> 00:05:12,520
And third, it could be a node which has two children.

118
00:05:12,520 --> 00:05:17,920
So these are the three possibilities right now let's see how to tackle these possibilities.

119
00:05:17,920 --> 00:05:19,810
Now let's say it's a leaf node.

120
00:05:19,810 --> 00:05:23,140
So let's say we just want to remove a node which is a leaf node.

121
00:05:23,140 --> 00:05:27,130
For example let's say we want to delete the node with value 25.

122
00:05:27,130 --> 00:05:28,990
And you can see that it's a leaf node.

123
00:05:28,990 --> 00:05:31,510
So first we have to find that node right.

124
00:05:31,510 --> 00:05:32,890
So that's the first step.

125
00:05:32,890 --> 00:05:35,050
And we have already discussed how we can do that.

126
00:05:35,050 --> 00:05:35,290
Right.

127
00:05:35,290 --> 00:05:41,170
So we start at 20 and then we move in the right direction because 25 is greater than 20.

128
00:05:41,170 --> 00:05:42,580
Then we reach 35.

129
00:05:42,580 --> 00:05:46,690
We move in the left direction because 25 is less than 35.

130
00:05:46,690 --> 00:05:48,310
And then we reach 27.

131
00:05:48,310 --> 00:05:52,330
And again we move in the left direction because 25 is less than 27.

132
00:05:52,330 --> 00:05:57,370
So we have found the node which is to be deleted because 25 is equal to 25.

133
00:05:57,370 --> 00:06:03,010
Now at this point, because this is a leaf node, all we need to do is just we need to replace this

134
00:06:03,010 --> 00:06:03,460
with null.

135
00:06:03,460 --> 00:06:03,760
Right.

136
00:06:03,760 --> 00:06:05,890
So there's there's nothing else to be done.

137
00:06:05,890 --> 00:06:08,650
Now replacing this with null means the parent.

138
00:06:08,650 --> 00:06:10,450
This is the parent right of 25.

139
00:06:10,450 --> 00:06:14,290
We have to say this node the parent let me just call it p.

140
00:06:14,290 --> 00:06:15,220
So this is the parent.

141
00:06:15,220 --> 00:06:19,960
We have to say parent dot left is equal to null in this case.

142
00:06:20,560 --> 00:06:23,290
So in this way we have replaced this node with null.

143
00:06:23,290 --> 00:06:25,780
And that's deleting a leaf node.

144
00:06:25,780 --> 00:06:27,520
So we are done with this case over here.

145
00:06:27,520 --> 00:06:29,650
Now let's proceed to the second case.

146
00:06:29,650 --> 00:06:33,130
And let's say we want to delete a node which has only one child.

147
00:06:33,130 --> 00:06:35,890
For example let's say we want to delete 55.

148
00:06:35,890 --> 00:06:36,430
All right.

149
00:06:36,430 --> 00:06:38,350
So let me just clear this up a bit.

150
00:06:39,350 --> 00:06:43,400
Now the first step is again to find the node which is to be deleted.

151
00:06:43,400 --> 00:06:43,700
Right.

152
00:06:43,700 --> 00:06:49,400
So we have to find this node which is similar to what we discussed over here and in the first case as

153
00:06:49,400 --> 00:06:49,790
well.

154
00:06:49,790 --> 00:06:55,220
So once we have found this node now we need to know that this is a left child.

155
00:06:55,220 --> 00:06:55,400
Right.

156
00:06:55,400 --> 00:06:57,230
So this is a left child of this parent.

157
00:06:57,230 --> 00:07:00,470
So we have to say oh sorry this is a right child right.

158
00:07:00,470 --> 00:07:01,640
So this is a right child.

159
00:07:01,640 --> 00:07:03,470
Let me just write this over here.

160
00:07:03,470 --> 00:07:04,460
This is a right child.

161
00:07:04,460 --> 00:07:06,800
So we have to say parent dot right.

162
00:07:06,800 --> 00:07:07,070
Right.

163
00:07:07,070 --> 00:07:09,560
Parent dot right is equal to 60.

164
00:07:09,560 --> 00:07:11,540
So that's how we delete this node right.

165
00:07:11,540 --> 00:07:15,020
So parent dot right has to be equal to 60.

166
00:07:15,740 --> 00:07:16,100
All right.

167
00:07:16,100 --> 00:07:17,630
So this is again a right child.

168
00:07:17,630 --> 00:07:20,240
So parent dot right is equal to 60.

169
00:07:20,240 --> 00:07:21,980
And that's how we delete this.

170
00:07:21,980 --> 00:07:24,920
So these two cases are pretty straightforward right.

171
00:07:24,920 --> 00:07:27,860
If it's a leaf node we have to just set it to null.

172
00:07:27,860 --> 00:07:31,580
And in this case what we did is parent dot left is equal to null.

173
00:07:31,580 --> 00:07:33,140
So that's how we made this null.

174
00:07:33,140 --> 00:07:39,500
Now if it has only one child we have to say parent dot right or dot left depending whether the node

175
00:07:39,500 --> 00:07:41,780
to be deleted is a left child or a right child.

176
00:07:41,780 --> 00:07:45,680
And then we have to set that to the child of this particular node.

177
00:07:45,680 --> 00:07:47,960
And again remember it has only one child.

178
00:07:47,960 --> 00:07:52,370
So if it has a right child then we say parent dot right is the right child.

179
00:07:52,370 --> 00:07:56,060
And let's say it had only a left child, like for example, this was not there.

180
00:07:56,060 --> 00:08:01,940
And let's say it just had a node 54 over here in this case also because this is over here, a right

181
00:08:01,940 --> 00:08:07,130
child, we have to say parent dot right is equal to this 54 over here, which is equivalent to making

182
00:08:07,130 --> 00:08:08,120
this connection.

183
00:08:08,120 --> 00:08:08,720
All right.

184
00:08:08,720 --> 00:08:15,380
So we have discussed how to tackle these two cases which is deleting a leaf node and deleting a node

185
00:08:15,380 --> 00:08:16,940
which has only one child.

186
00:08:16,940 --> 00:08:21,440
Now let's proceed to the third case which is deleting a node which has two children.

187
00:08:21,440 --> 00:08:24,980
Now for example let's say we want to delete the node 20.

188
00:08:25,010 --> 00:08:29,210
Now over here 20 is a node which has two children, right?

189
00:08:29,210 --> 00:08:30,380
Six and 35.

190
00:08:30,380 --> 00:08:32,840
Now the first step is again finding the node.

191
00:08:32,840 --> 00:08:34,670
Right now we start at the root node.

192
00:08:34,670 --> 00:08:38,510
And because over here 20 is the root node itself we have found the node.

193
00:08:38,510 --> 00:08:41,600
Now if it was not the case let's say we wanted to delete 35.

194
00:08:41,630 --> 00:08:43,010
The same procedure follows.

195
00:08:43,010 --> 00:08:44,450
We have to start at 20.

196
00:08:44,450 --> 00:08:45,200
Move to the right.

197
00:08:45,200 --> 00:08:47,810
And then we find the node which has to be deleted.

198
00:08:47,810 --> 00:08:48,500
All right.

199
00:08:48,890 --> 00:08:53,210
Now once we have found the node which is to be deleted.

200
00:08:54,090 --> 00:09:01,260
The next step is to replace that particular node, which is to be deleted with its in-order predecessor

201
00:09:01,260 --> 00:09:02,520
or successor.

202
00:09:02,550 --> 00:09:03,870
Now, what do I mean with this?

203
00:09:03,870 --> 00:09:09,180
Now, in the next question, we will deal with in-order traversal depth.

204
00:09:09,180 --> 00:09:13,170
First search of in-order type of a binary search tree.

205
00:09:13,170 --> 00:09:14,580
So there is a different question for that.

206
00:09:14,580 --> 00:09:15,870
So you can go and refer that.

207
00:09:15,870 --> 00:09:21,660
Now when we you will see it over there that when you do in-order traversal on a binary search tree,

208
00:09:21,660 --> 00:09:24,120
you will get the elements in ascending order.

209
00:09:24,120 --> 00:09:24,420
Right.

210
00:09:24,420 --> 00:09:32,430
So let's just write 20 over here and what would be its previous number, let's say over all the elements

211
00:09:32,430 --> 00:09:36,390
over here are written in ascending order, that is, from the smallest to the largest.

212
00:09:36,390 --> 00:09:42,480
Now if we just do that, you can see that you will have eight and then you will have 20, and then you

213
00:09:42,480 --> 00:09:43,560
will have 25.

214
00:09:43,560 --> 00:09:43,860
Right.

215
00:09:43,860 --> 00:09:45,030
And then it will go on like that.

216
00:09:45,030 --> 00:09:45,360
Right.

217
00:09:45,360 --> 00:09:51,390
So again just refer the video where we discuss in-order traversal of a binary search tree.

218
00:09:51,390 --> 00:09:52,410
And there you can see that.

219
00:09:52,410 --> 00:09:55,740
So when you do that you will get the elements in ascending order right.

220
00:09:55,740 --> 00:09:57,720
So over here also let's just write it out.

221
00:09:57,720 --> 00:10:02,070
If you do, if you arrange all these elements in ascending order, how would it look like.

222
00:10:02,070 --> 00:10:02,970
So we have one.

223
00:10:02,970 --> 00:10:03,930
Then we have three.

224
00:10:03,930 --> 00:10:09,810
We have three, then we have six, then we have eight, then we have 20, then we have 25.

225
00:10:09,810 --> 00:10:10,200
Right.

226
00:10:10,200 --> 00:10:11,400
So it goes on like that.

227
00:10:11,400 --> 00:10:12,870
Then we have 27.

228
00:10:12,870 --> 00:10:18,480
Then you have 29, then you have 35, 55 and 60.

229
00:10:18,480 --> 00:10:19,830
So this is the ascending order.

230
00:10:19,830 --> 00:10:25,920
So if you were to do in-order traversal of the binary search tree, you and then you print all the elements

231
00:10:25,920 --> 00:10:27,990
into an array.

232
00:10:27,990 --> 00:10:32,970
For example, you store all the elements in an array and you just um, print that array.

233
00:10:32,970 --> 00:10:34,620
So then it would look like this.

234
00:10:34,620 --> 00:10:35,220
All right.

235
00:10:35,220 --> 00:10:38,280
So over here we have 20 which is the node to be deleted.

236
00:10:38,280 --> 00:10:41,160
So now what we need to do is we found the node.

237
00:10:41,160 --> 00:10:45,840
And now we need to replace it with its in-order predecessor or successor.

238
00:10:45,840 --> 00:10:49,350
So the predecessor of 20 is eight over here.

239
00:10:49,350 --> 00:10:52,110
And the successor of 20 is 25.

240
00:10:52,110 --> 00:10:52,530
All right.

241
00:10:52,530 --> 00:10:55,590
So again just repeating what we have to do.

242
00:10:55,590 --> 00:10:57,900
The first step is finding the node to be deleted.

243
00:10:57,900 --> 00:11:02,670
And the second step is replacing it with its in-order predecessor or successor.

244
00:11:02,670 --> 00:11:06,390
Now let me just clear this up and let's see how we do this.

245
00:11:06,390 --> 00:11:10,890
So I just wanted to mention this over here because you will see this in different sources.

246
00:11:10,890 --> 00:11:11,250
Right.

247
00:11:11,250 --> 00:11:15,450
So I just wanted you to be aware what is the in-order predecessor and successor.

248
00:11:15,510 --> 00:11:19,320
And again, it's just a technicality right now.

249
00:11:19,320 --> 00:11:21,210
Let's see how we proceed with this.

250
00:11:21,210 --> 00:11:28,320
Now, the in-order successor or the next greatest value after the node which is to be deleted, will

251
00:11:28,320 --> 00:11:32,010
be the smallest node in the right subtree.

252
00:11:32,010 --> 00:11:34,110
So this is the right subtree of 20, right.

253
00:11:34,110 --> 00:11:35,910
So this is the right side of 20 right.

254
00:11:35,910 --> 00:11:39,060
So if you take the smallest value of this you will get 25.

255
00:11:39,060 --> 00:11:43,290
So that will be the in-order successor of the node to be deleted.

256
00:11:43,290 --> 00:11:44,820
Now what about the predecessor.

257
00:11:44,820 --> 00:11:49,320
The predecessor would be the largest value in the left subtree.

258
00:11:49,320 --> 00:11:52,500
You can see that the largest value over here is eight right.

259
00:11:52,500 --> 00:11:54,600
So you can proceed in either way.

260
00:11:54,600 --> 00:11:57,720
So you can either replace 20 with eight.

261
00:11:57,720 --> 00:12:01,980
So if you do that let's say for example you write eight over here and you remove this, you can see

262
00:12:01,980 --> 00:12:04,530
that this follows the binary search tree property.

263
00:12:04,530 --> 00:12:04,740
Right.

264
00:12:04,740 --> 00:12:09,750
Everything on its left is less than eight and everything on its right is greater than eight.

265
00:12:09,750 --> 00:12:14,790
So that's why we are actually taking one of these two elements and putting it on the on the node, which

266
00:12:14,790 --> 00:12:15,660
is to be deleted, right?

267
00:12:15,660 --> 00:12:17,310
So that the property is maintained.

268
00:12:17,310 --> 00:12:21,750
You can see if you put eight over here, everything on its left is still less than eight and everything

269
00:12:21,750 --> 00:12:23,250
on its right is still greater than eight.

270
00:12:23,250 --> 00:12:30,240
Now you could also replace this 20 with this 25, which is the smallest element in the right subtree.

271
00:12:30,240 --> 00:12:32,460
So let's say we put 25 over here.

272
00:12:32,460 --> 00:12:38,760
If you put 25 over here, you can see everything on its left is less than 25 and everything on its right

273
00:12:38,760 --> 00:12:39,840
is greater than 25.

274
00:12:39,840 --> 00:12:44,340
Right now, everything on its right will be greater than 25, because this is the smallest element in

275
00:12:44,340 --> 00:12:45,060
the right subtree.

276
00:12:45,060 --> 00:12:46,980
So that's the logic behind this.

277
00:12:46,980 --> 00:12:49,980
Now let's go ahead and take one of these approaches.

278
00:12:49,980 --> 00:12:50,220
Right.

279
00:12:50,220 --> 00:12:51,900
You can go with either approach.

280
00:12:51,900 --> 00:12:58,320
Now in this video we will go with the approach where we find the smallest element in the right subtree.

281
00:12:58,320 --> 00:13:00,150
So that's the approach we are going to take.

282
00:13:00,150 --> 00:13:00,780
All right.

283
00:13:01,200 --> 00:13:02,730
So this is the right subtree.

284
00:13:02,730 --> 00:13:06,930
And we are trying to find the smallest element in this right subtree.

285
00:13:06,930 --> 00:13:14,160
And you will notice that the smallest element in this right subtree will be the left most element right.

286
00:13:14,160 --> 00:13:15,030
Why is that so?

287
00:13:15,030 --> 00:13:19,890
Because whenever we have something which is less than the node right, we always move in the left direction,

288
00:13:19,890 --> 00:13:20,160
right?

289
00:13:20,160 --> 00:13:23,340
So for example let's say you wanted to insert 25.

290
00:13:23,340 --> 00:13:26,280
So you started and let's say 35 is the node right.

291
00:13:26,280 --> 00:13:28,710
So this is let's consider this as a subtree.

292
00:13:28,710 --> 00:13:32,580
So the node of this subtree let's say it's 35 right.

293
00:13:32,580 --> 00:13:34,350
So 25 is less than 35.

294
00:13:34,350 --> 00:13:35,820
So you move in the left direction.

295
00:13:35,820 --> 00:13:37,980
Now 25 is less than 27.

296
00:13:37,980 --> 00:13:39,690
Again you move in the left direction right.

297
00:13:39,690 --> 00:13:44,640
So we just need to find the left most element to find the smallest element.

298
00:13:44,640 --> 00:13:51,060
Now in the same manner, if you were to find the largest element in this left subtree, you you should

299
00:13:51,060 --> 00:13:53,280
have found the right most element right.

300
00:13:53,280 --> 00:13:53,580
So.

301
00:13:53,730 --> 00:13:56,310
The right most element will be the largest element.

302
00:13:56,310 --> 00:13:56,730
All right.

303
00:13:56,730 --> 00:13:57,930
So that was just a sub point.

304
00:13:57,930 --> 00:14:02,370
So let's proceed and see how we can find the left most element.

305
00:14:02,370 --> 00:14:03,510
And then what should we do.

306
00:14:04,300 --> 00:14:07,660
So again, let's say we have this node.

307
00:14:07,660 --> 00:14:11,590
We know that we need to find the left most element in this subtree.

308
00:14:11,590 --> 00:14:14,650
So we just keep moving left as long as we can.

309
00:14:14,650 --> 00:14:17,860
Right now if we move left after this we get to null right.

310
00:14:17,860 --> 00:14:19,840
So the left of this node over here is null.

311
00:14:19,840 --> 00:14:24,700
So then we know that we have found the left most element and that will be the smallest element.

312
00:14:24,700 --> 00:14:27,370
Now what we need to do is we need to take this value.

313
00:14:27,370 --> 00:14:31,570
And we replace and put that value on the node which is to be deleted.

314
00:14:31,570 --> 00:14:33,490
So we wanted to delete this 20 node.

315
00:14:33,490 --> 00:14:33,790
Right.

316
00:14:33,790 --> 00:14:38,230
So we take we find this left most element and we put this value over here.

317
00:14:38,230 --> 00:14:38,890
All right.

318
00:14:38,890 --> 00:14:42,070
Now what we need to do is we need to change this to null.

319
00:14:42,070 --> 00:14:42,730
And we are done.

320
00:14:42,730 --> 00:14:43,060
Right.

321
00:14:43,060 --> 00:14:43,990
So that's all.

322
00:14:43,990 --> 00:14:48,460
So we just need to find the left most element and then put that value over here.

323
00:14:48,460 --> 00:14:50,350
And then we need to change this to null.

324
00:14:50,350 --> 00:14:52,750
So how do we do this again.

325
00:14:52,750 --> 00:14:54,760
For this we will have a function.

326
00:14:54,760 --> 00:14:58,930
And we will recursively call that function on this subtree with the new value.

327
00:14:58,930 --> 00:14:59,440
All right.

328
00:14:59,440 --> 00:15:04,480
So initially we call the remove function on the whole binary search tree.

329
00:15:04,480 --> 00:15:06,610
And we pass in the value 20.

330
00:15:06,610 --> 00:15:08,140
So that finds 20.

331
00:15:08,170 --> 00:15:14,050
Then we will have a function which will find the minimum value from the right subtree.

332
00:15:14,080 --> 00:15:19,000
We get that value back and we put it over here which is on the node which is to be deleted.

333
00:15:19,000 --> 00:15:25,780
Then we again call the remove function on the right subtree and we pass the value 25 at this time,

334
00:15:25,780 --> 00:15:32,080
initially, the value 20 was passed because we wanted to delete that right now in this right subtree,

335
00:15:32,080 --> 00:15:36,820
we just want to delete the value with the node with value 25, because we don't want to duplicate it.

336
00:15:36,820 --> 00:15:37,090
Right.

337
00:15:37,090 --> 00:15:39,850
So we again recursively call the remove function.

338
00:15:39,850 --> 00:15:44,110
But at this point the space complexity will not improve, will not increase.

339
00:15:44,110 --> 00:15:46,420
Because you can see that we are just calling it two times.

340
00:15:46,420 --> 00:15:48,970
It's not we are not implementing a recursive solution.

341
00:15:48,970 --> 00:15:53,410
Over here we are discussing an iterative solution, but we have a recursive call which is happening

342
00:15:53,410 --> 00:15:54,220
only one time.

343
00:15:54,220 --> 00:15:57,250
So we call it on the right subtree to delete this node.

344
00:15:57,250 --> 00:15:57,820
All right.

345
00:15:57,850 --> 00:16:00,010
Now there is also one more possibility.

346
00:16:00,010 --> 00:16:04,660
Let's say this node 25 over here had a right child, which is 26.

347
00:16:04,660 --> 00:16:06,490
What would have happened in this case?

348
00:16:06,490 --> 00:16:10,210
In this case also the leftmost element is still 25, right.

349
00:16:10,210 --> 00:16:16,150
So we find 25 and we put the value of 25 on the node which is to be deleted, which is 20 over here.

350
00:16:16,150 --> 00:16:21,730
And then we say that 27 dot left is 26 or its child.

351
00:16:21,730 --> 00:16:22,000
Right.

352
00:16:22,000 --> 00:16:25,930
So 27 dot left is 26 which is the child of it.

353
00:16:25,930 --> 00:16:30,490
So again that's similar to deleting a node with one child, which is something that we have already

354
00:16:30,490 --> 00:16:31,060
discussed.

355
00:16:31,060 --> 00:16:37,420
So this is how we handle deleting a node which has two children.

356
00:16:37,420 --> 00:16:38,080
All right.

357
00:16:38,080 --> 00:16:40,900
Now again remember to do this operation over here.

358
00:16:40,900 --> 00:16:42,430
That is either to set 20.

359
00:16:42,460 --> 00:16:46,210
This node over here to null and 27 dot left will be null.

360
00:16:46,210 --> 00:16:50,980
Or if it had a child 27 dot left will be this 26 over here.

361
00:16:50,980 --> 00:16:55,090
And again there will not be a case where you have a child, a left child for 25, right?

362
00:16:55,090 --> 00:16:57,940
Because in that case that would be the left most element.

363
00:16:57,940 --> 00:16:58,360
All right.

364
00:16:58,360 --> 00:17:02,290
So over here we just set 27 dot left is 26.

365
00:17:02,290 --> 00:17:06,670
Now to do this we recursively call the remove function one more time.

366
00:17:06,670 --> 00:17:07,120
All right.

367
00:17:07,120 --> 00:17:09,460
So that's how we do the remove function.

368
00:17:09,460 --> 00:17:11,770
And we have discussed the three possibilities.

369
00:17:11,770 --> 00:17:14,710
The possibility where the node to be deleted is a leaf node.

370
00:17:14,710 --> 00:17:17,770
The possibility where it's a node with only one child.

371
00:17:17,770 --> 00:17:22,900
And the third possibility where the node to be deleted is a node which has two children.

372
00:17:22,900 --> 00:17:28,600
So in this case, we find the smallest element in the right subtree.

373
00:17:28,630 --> 00:17:31,420
We put that value on the node which is to be deleted.

374
00:17:31,420 --> 00:17:34,450
And then we just remove that node from the right subtree.

375
00:17:34,450 --> 00:17:34,990
All right.

376
00:17:35,020 --> 00:17:39,280
Now let's quickly look at the complexity analysis of this solution which we discussed.

377
00:17:39,310 --> 00:17:47,830
Now the time complexity for insert, remove and find will be O of log n best and average case, and

378
00:17:47,830 --> 00:17:50,650
it will be O of n in the worst case.

379
00:17:50,650 --> 00:17:52,360
Now let's try to understand this.

380
00:17:52,690 --> 00:17:58,780
Now over here for inserting or removing or finding the number of operations is happening because we

381
00:17:58,780 --> 00:17:59,800
need to find it, right.

382
00:17:59,800 --> 00:18:06,010
We need to find the node which is to be in the the correct place for inserting the node or the node

383
00:18:06,010 --> 00:18:08,440
which is to be removed, or searching for the node.

384
00:18:08,440 --> 00:18:08,680
Right.

385
00:18:08,680 --> 00:18:12,520
So we need to do a set of comparisons to reach to the correct place.

386
00:18:12,520 --> 00:18:19,180
So the number of comparisons will be equal to log n in the case that the tree is balanced.

387
00:18:19,180 --> 00:18:19,630
Right.

388
00:18:19,630 --> 00:18:25,720
So that's why we say that the time complexity is O of log n in the best and average case.

389
00:18:25,720 --> 00:18:28,210
So it's nothing but the height of the tree, right.

390
00:18:28,210 --> 00:18:29,860
In the case it's a balanced tree.

391
00:18:29,890 --> 00:18:35,230
Now why do we say that it's not always O of log n because there is a possibility like this, right.

392
00:18:35,230 --> 00:18:38,770
If you have let's say a binary search tree like this.

393
00:18:38,770 --> 00:18:43,540
Now this looks like a linked list, but in fact this is a valid binary search tree.

394
00:18:43,540 --> 00:18:46,000
Let's say you inserted one, then you insert two.

395
00:18:46,030 --> 00:18:47,320
So two is greater than one.

396
00:18:47,320 --> 00:18:49,360
So you insert it on its right right.

397
00:18:49,360 --> 00:18:51,670
Then again you insert a node with value three.

398
00:18:51,670 --> 00:18:53,200
So that is also greater than two.

399
00:18:53,230 --> 00:18:54,670
So it goes to the right of two.

400
00:18:54,670 --> 00:18:56,590
And then you insert a node with value four.

401
00:18:56,590 --> 00:18:59,110
So that also goes to the right of three.

402
00:18:59,110 --> 00:19:01,390
So this is a valid binary search tree.

403
00:19:01,390 --> 00:19:03,100
But it looks like a linked list right.

404
00:19:03,100 --> 00:19:03,850
And that's why.

405
00:19:04,020 --> 00:19:04,350
I.

406
00:19:04,800 --> 00:19:08,910
If you want to insert something, we would have to go in all this way, right?

407
00:19:08,910 --> 00:19:10,380
Let's say you want to insert five.

408
00:19:10,380 --> 00:19:14,130
You have to do n number of comparisons and insert five over here.

409
00:19:14,130 --> 00:19:18,810
So that's why we say that the worst case time complexity is O of n.

410
00:19:18,810 --> 00:19:22,500
In the case of a binary search tree for insert, remove and find.

411
00:19:22,500 --> 00:19:23,070
All right.

412
00:19:23,100 --> 00:19:24,840
Now how do we solve this.

413
00:19:24,840 --> 00:19:27,990
The best way to solve this is don't take one as a root.

414
00:19:27,990 --> 00:19:30,300
Let's say for example you take two as root.

415
00:19:30,330 --> 00:19:32,760
Now the binary search tree would look like this.

416
00:19:32,760 --> 00:19:38,070
Right now in this case, the number of comparisons you have to do is just log n which is log four.

417
00:19:38,070 --> 00:19:40,140
In this case because you have four roots right?

418
00:19:40,140 --> 00:19:40,860
Four nodes.

419
00:19:40,860 --> 00:19:45,720
So the number of maximum number of comparisons you have to do is just log four which is equal to two.

420
00:19:45,750 --> 00:19:50,340
Now also notice over here log n is the minimum possible height right.

421
00:19:50,340 --> 00:19:52,950
So that's why we say it's the best case.

422
00:19:52,950 --> 00:19:55,260
Also this is the minimum possible height right.

423
00:19:55,260 --> 00:19:56,400
If you have n nodes.

424
00:19:56,400 --> 00:19:58,560
And if you are making a binary search tree.

425
00:19:58,560 --> 00:20:00,930
So the minimum possible height is log n.

426
00:20:00,930 --> 00:20:05,100
Now you can have a greater height like for example over here right 1234.

427
00:20:05,100 --> 00:20:06,900
So over here the height is not two right.

428
00:20:06,900 --> 00:20:08,730
But in this case the height is two.

429
00:20:08,730 --> 00:20:11,160
So the minimum height is also log n.

430
00:20:11,160 --> 00:20:11,790
All right.

431
00:20:11,820 --> 00:20:15,060
Now let's also look at the space complexity.

432
00:20:15,060 --> 00:20:20,940
We have seen that the time complexity is O of log n best and average and O of n in the worst case.

433
00:20:20,940 --> 00:20:23,130
Now what about the space complexity.

434
00:20:23,160 --> 00:20:29,580
Now the space complexity will depend on the approach you take to implement these functions the insert,

435
00:20:29,580 --> 00:20:31,290
remove and find functions.

436
00:20:31,800 --> 00:20:36,480
Now you can implement this insert, remove and find function in two ways.

437
00:20:36,480 --> 00:20:42,870
If you do it recursively, then the space complexity will be O of log n average and worst case.

438
00:20:42,870 --> 00:20:45,930
Now in the worst case you will have n calls on the call stack.

439
00:20:45,930 --> 00:20:49,380
Right now, in the average and best case you will have log n calls.

440
00:20:49,380 --> 00:20:54,870
So that's why we say that the space complexity is O of log n average and best case and O of n worst

441
00:20:54,870 --> 00:20:55,320
case.

442
00:20:55,320 --> 00:21:01,680
Now if you do it iteratively like we have discussed, and in this video and in this code section, we

443
00:21:01,680 --> 00:21:03,960
will be implementing this in the iterative manner.

444
00:21:03,960 --> 00:21:09,150
And you will see that this has a better space complexity, which is O of one, because we are not going

445
00:21:09,150 --> 00:21:12,510
to have uh n or log n calls on the call stack.

446
00:21:12,510 --> 00:21:16,740
Now also notice over here one extra call is there on the call stack.

447
00:21:16,740 --> 00:21:19,500
But again O of two is nothing but O of one itself, right?

448
00:21:19,500 --> 00:21:21,150
If you say that it's O of two.

449
00:21:21,180 --> 00:21:23,490
The space complexity, this is just a constant.

450
00:21:23,490 --> 00:21:28,620
So we say the space complexity is O of one itself if we implement it iteratively.

451
00:21:28,620 --> 00:21:30,930
And that's how we are going to do it in this video.