1
00:00:00,520 --> 00:00:05,260
OK, so going back to a another lecture on binary search trees.

2
00:00:06,210 --> 00:00:15,410
In this lecture, we are going to go over the theoretical and actual implementation, part of a another

3
00:00:15,420 --> 00:00:22,830
specific function for binary searches, another algorithm and that is going to be the function that

4
00:00:22,830 --> 00:00:29,970
finds the K the smallest value in the binary search tree.

5
00:00:31,050 --> 00:00:38,280
And so this is a pretty popular algorithm to be asked in interviews or, you know, so as far as I've

6
00:00:38,280 --> 00:00:38,670
heard.

7
00:00:39,570 --> 00:00:45,990
And so that's why I wanted to cover it since we're kind of going over a limited amount of functions

8
00:00:45,990 --> 00:00:48,900
with binary search trees other than the basics.

9
00:00:50,730 --> 00:00:59,250
So basically, it's just like it sounds the user or the client file would ask for.

10
00:00:59,550 --> 00:01:09,210
They provide a number and that number or integer, if you will, will be the case value for the K,

11
00:01:09,210 --> 00:01:14,010
the smallest value in the binary search tree in which we will need to return.

12
00:01:14,740 --> 00:01:15,080
Hmm.

13
00:01:16,350 --> 00:01:22,740
And so I definitely invite you to pause the video or stop now and take your time and see if you can

14
00:01:22,740 --> 00:01:24,600
solve this on your own.

15
00:01:24,990 --> 00:01:32,760
I did not include it as an exercise because in my opinion, this is one of the harder binary search

16
00:01:32,760 --> 00:01:33,780
tree algorithms.

17
00:01:34,980 --> 00:01:41,850
Some people may not agree with me, but I found it to be a little bit more difficult than the other

18
00:01:41,850 --> 00:01:42,210
ones.

19
00:01:42,460 --> 00:01:46,710
I'm not really sure why, but definitely made me want to cover it.

20
00:01:46,720 --> 00:01:51,870
So if you want to figure this out, go ahead and post the video and see if you can solve this on your

21
00:01:51,870 --> 00:01:52,080
own.

22
00:01:52,080 --> 00:01:53,280
Otherwise I will walk through it.

23
00:01:55,870 --> 00:01:56,290
OK.

24
00:01:56,740 --> 00:02:00,220
So of course, congratulations if you were able to figure it out.

25
00:02:00,730 --> 00:02:06,180
Of course, a lot of there's, you know, different ways to do this.

26
00:02:06,190 --> 00:02:07,480
I won't say a lot of different ways.

27
00:02:08,110 --> 00:02:20,500
But the main idea is going to be that since we are looking for the smallest, we kind of want to start

28
00:02:20,500 --> 00:02:23,230
at the smallest and go up from there.

29
00:02:23,300 --> 00:02:28,030
And when you think about that, it's kind of like something being sorted in order.

30
00:02:29,000 --> 00:02:36,680
And we already have discussed a method of traversing this tree in order, and that is in order traversal.

31
00:02:37,760 --> 00:02:43,850
And if you recall correctly, that involves us going all the way to the left first to get to the smallest

32
00:02:43,850 --> 00:02:51,920
value and then kind of doing our thing, which would be like processing the node and then going to the

33
00:02:51,920 --> 00:02:52,310
right.

34
00:02:52,670 --> 00:02:57,350
And if we recall correctly, that is how the tree is kind of organized.

35
00:02:58,870 --> 00:03:00,700
It's organized like the left.

36
00:03:02,010 --> 00:03:06,930
It's basically like, you know, if you're going to give a no, let's say five, you know, the left

37
00:03:06,930 --> 00:03:09,720
is smaller and then comes five and then comes the right.

38
00:03:09,810 --> 00:03:12,540
So it's like left middle, right kind of.

39
00:03:12,810 --> 00:03:14,250
And that is the in order to wrestle.

40
00:03:14,820 --> 00:03:21,930
So it would be a good idea for us to try and use the idea of in order traversal to solve this problem.

41
00:03:21,930 --> 00:03:24,270
And that's exactly what we're going to do.

42
00:03:24,750 --> 00:03:31,710
And now a solution might involve doing it in order traversal and then just kind of appending to another

43
00:03:31,710 --> 00:03:35,610
container, which is that great idea if that's how you ended up doing it.

44
00:03:35,610 --> 00:03:42,150
If you attempted this on your own and you can kind of go left some tree call and then add it to a vector

45
00:03:42,150 --> 00:03:49,080
or something and write some tree call, you know, that might work out if that is, you know, another

46
00:03:49,080 --> 00:03:50,090
way that you like to do it.

47
00:03:50,100 --> 00:03:55,170
I'm just going to go over the just straight up recursive function that will return in the case smallest

48
00:03:55,170 --> 00:03:59,400
without using another data structure besides just traversing the tree itself.

49
00:03:59,410 --> 00:04:00,870
So that's how I'm going to do this.

50
00:04:02,150 --> 00:04:07,340
So let's go ahead and get started, I have an example here where Kaye starts out as five, so that means

51
00:04:07,340 --> 00:04:16,010
the user passed five to the function and I have this condition here because this is an important condition.

52
00:04:17,810 --> 00:04:26,600
We're going to use a strategy of subtracting from the value that the user has passed.

53
00:04:26,600 --> 00:04:33,110
And then once we reach zero, we are going to return the node because we will know that we are at the

54
00:04:33,110 --> 00:04:34,610
node with the answer.

55
00:04:34,690 --> 00:04:38,210
And so I'm going to set it up in a way where we can do it in order traversal.

56
00:04:39,480 --> 00:04:45,330
And we're going to do that like left call and then processing in which we will do the subtraction and

57
00:04:45,330 --> 00:04:46,740
then we will do the right call.

58
00:04:47,550 --> 00:04:49,710
So that's an order style reversal.

59
00:04:50,850 --> 00:04:52,410
And we will want a check.

60
00:04:53,380 --> 00:04:59,320
Before we do the right call, we will want a check to see if K is zero, and in that case, we know

61
00:04:59,320 --> 00:05:07,420
we've gotten to our answer and we will then return that node and that node will have the value assets

62
00:05:07,420 --> 00:05:10,300
data member that we will want to return to the client.

63
00:05:12,300 --> 00:05:14,610
All right, so let's go ahead and walk through this example.

64
00:05:14,730 --> 00:05:18,720
So if we were going to do that in order to wrestle, we'd want to go left all the way first.

65
00:05:18,720 --> 00:05:23,340
So we'd start at the route and we go to seven, five three and all the way down to no.

66
00:05:24,360 --> 00:05:28,830
We're going to want another probably a primary base case.

67
00:05:30,090 --> 00:05:32,160
As you know, if we reach no.

68
00:05:32,190 --> 00:05:36,600
We're going to want to just return that no back.

69
00:05:37,170 --> 00:05:41,760
So we don't have any problems there and we'll know that we're at a leaf node.

70
00:05:41,970 --> 00:05:43,620
So let's just assume that.

71
00:05:44,100 --> 00:05:49,560
So we're going to do recursion coming back from this novel because we've regional and it's a base case.

72
00:05:49,560 --> 00:05:50,520
So we return that.

73
00:05:52,260 --> 00:05:58,410
And then since we've returned that and we went left, you can imagine that we're coming back to our

74
00:05:58,410 --> 00:06:01,680
left recursion call here at this node.

75
00:06:02,190 --> 00:06:06,900
And so if we're doing that in order to wrestle, we are then going to want to process this node.

76
00:06:06,900 --> 00:06:12,930
So I'm going to note that with this yellow ring here, so we're processing the node, and since we're

77
00:06:12,930 --> 00:06:14,910
processing it, we're going to subtract.

78
00:06:15,330 --> 00:06:16,830
So we're going to subtract one.

79
00:06:16,980 --> 00:06:21,030
We'll do a K minus minus, and that'll bring us from five to four.

80
00:06:22,860 --> 00:06:29,890
And so then we want to check, you know, is K zero, no, K is not a zero, it's four.

81
00:06:29,920 --> 00:06:32,670
So let's go ahead and do our right recursion then.

82
00:06:32,970 --> 00:06:39,810
So we hit no down here for our right recursion, and then we'll have that initial base case where we're

83
00:06:39,810 --> 00:06:41,250
returning null.

84
00:06:41,850 --> 00:06:43,830
If we encounter no, we're going to return it back.

85
00:06:44,280 --> 00:06:46,410
So we do that and we return now back to here.

86
00:06:47,900 --> 00:06:56,510
And now that we've processed both of these, we're going to go ahead and return back up to here because

87
00:06:56,510 --> 00:07:01,760
we've done like a fall in order to kind of to of this zone right here the submarine.

88
00:07:02,900 --> 00:07:09,230
And so you can notice that since we're coming back up here, we just finished a little left sabiri call

89
00:07:09,230 --> 00:07:12,200
from this stack, frame this node.

90
00:07:13,610 --> 00:07:18,110
And so we're going to move to that next part, which is processing.

91
00:07:18,380 --> 00:07:25,670
So we're going to go ahead and process this node and we will subtract and we'll check again as K0 Care's

92
00:07:25,670 --> 00:07:26,510
not zero.

93
00:07:26,600 --> 00:07:29,690
So let's go ahead and do the right recursion.

94
00:07:30,020 --> 00:07:31,390
So we do the right recursion.

95
00:07:31,400 --> 00:07:32,240
We come here.

96
00:07:33,750 --> 00:07:39,180
Then once we do our right recursion, you know what we're going to do, and I want to note is we still

97
00:07:39,180 --> 00:07:43,950
going to follow that left first, then process, then right.

98
00:07:44,460 --> 00:07:47,810
So we're going to go left and that's going to be null.

99
00:07:47,820 --> 00:07:54,210
And so we will return back with that null from our initial base case, which is going to be if we're

100
00:07:54,210 --> 00:07:57,720
at no and we're going to return null, then we'll do our processing.

101
00:07:58,350 --> 00:08:00,750
So let's do another minus minus two.

102
00:08:00,750 --> 00:08:05,070
Now check K is two, it's not zero.

103
00:08:05,070 --> 00:08:06,690
So it's to our right recursion.

104
00:08:06,690 --> 00:08:07,620
We hit no again.

105
00:08:07,620 --> 00:08:08,790
So we return back.

106
00:08:09,550 --> 00:08:11,200
We've processed both of these.

107
00:08:11,220 --> 00:08:15,130
So we were going to return back up to here again, which is still that null.

108
00:08:15,490 --> 00:08:16,800
You know, we can't return nil.

109
00:08:16,800 --> 00:08:17,670
Return nil again.

110
00:08:18,030 --> 00:08:19,350
Return back up to here.

111
00:08:20,450 --> 00:08:25,070
And then now we've processed the left and right for this, so we're going to return back up to here

112
00:08:25,700 --> 00:08:30,110
and now, if you're thinking about the function again, kind of like pseudocode in your head.

113
00:08:30,440 --> 00:08:36,440
Remember once again that now we're coming from this left sub trickle of this stack frame.

114
00:08:37,530 --> 00:08:38,970
And we've gotten A..

115
00:08:39,660 --> 00:08:49,260
So we're going to then go to the next part since we've done the left call and we're going to process

116
00:08:49,410 --> 00:08:49,870
this.

117
00:08:50,550 --> 00:08:52,320
And then we're going to do a subtraction again.

118
00:08:52,320 --> 00:08:56,080
So now we're at one one is not zero, so let's go ahead and do the right.

119
00:08:56,700 --> 00:09:00,330
So we go to the right, then we can do that whole thing over again.

120
00:09:00,330 --> 00:09:03,840
You know where we have to go to the left first and then process and then go to the right.

121
00:09:03,840 --> 00:09:06,960
So we go to the left first from here and then it's null.

122
00:09:06,960 --> 00:09:08,730
So we return that no backup.

123
00:09:09,720 --> 00:09:14,700
Let's go ahead and process, we process it so that we're going to do the subtraction as part as our

124
00:09:14,700 --> 00:09:15,660
processing the known.

125
00:09:17,730 --> 00:09:24,120
Check is K zero, K is zero, so we're not going to do the right recursive call now, we're just going

126
00:09:24,120 --> 00:09:30,270
to return node, so let's return the node back up to here and we return to the node up to here.

127
00:09:30,600 --> 00:09:35,770
And you notice that this has had the left subtropical completed and its tenants rights have to be called

128
00:09:35,790 --> 00:09:36,300
completed.

129
00:09:36,300 --> 00:09:42,630
So this return node comes back up to here and the function is done, and so it's going to return back

130
00:09:42,630 --> 00:09:43,230
up to here.

131
00:09:44,160 --> 00:09:52,500
And so while now we have our answer, eight was the fifth smallest value in our tree.

132
00:09:52,500 --> 00:09:59,130
So one two three four five fifth smallest value.

133
00:10:00,340 --> 00:10:02,830
OK, so hopefully that explain it theoretically enough.

134
00:10:03,340 --> 00:10:06,220
Let's go ahead and implement this thing in code.

135
00:10:06,820 --> 00:10:08,940
So I'm going to head over to Sea Lion.

136
00:10:08,950 --> 00:10:11,920
I've already had it pulled out and unclear this.

137
00:10:13,770 --> 00:10:22,530
I'm in the header file of our binary search, B, T H, and I'm going to go ahead and put just like

138
00:10:22,530 --> 00:10:26,730
we've been doing before, I'm going to have a public facing method and a private one.

139
00:10:26,940 --> 00:10:33,930
So let's make the public function here where we get the integer K from the user.

140
00:10:34,770 --> 00:10:39,660
So that is just going to return an integer because we'll want to return the actual K the smallest.

141
00:10:39,660 --> 00:10:47,070
And so I'm going to call it case smallest, and it's going to take that integer from the user K.

142
00:10:48,520 --> 00:10:54,040
Then I'll make the private one here, and it's going to turn the node that has the data we're looking

143
00:10:54,040 --> 00:10:54,340
for.

144
00:10:54,370 --> 00:11:00,940
So that's going to be a trainload pointer also going to call it K smallest and then it's going to basically

145
00:11:00,940 --> 00:11:05,440
recursively need to pass the sub trees, which will be like a node.

146
00:11:05,980 --> 00:11:11,560
And so that's going to have a tree node pointer node is what I'm going to call it.

147
00:11:11,560 --> 00:11:17,200
And then we're going to have our, of course, our integer K and that's going to be passed by reference

148
00:11:17,530 --> 00:11:20,980
and we're going to be updating K and passing it recursively.

149
00:11:22,450 --> 00:11:29,910
So I have both these functions, the private and the public version of it for our client file.

150
00:11:30,950 --> 00:11:36,740
And I'm going to head over to the BPP file to implement this, so let's start off with that public facing

151
00:11:36,740 --> 00:11:39,560
one to the scope or solution there.

152
00:11:40,010 --> 00:11:44,960
Do care the smallest and the first thing I'm going to do is make sure that the user's not asking for

153
00:11:44,960 --> 00:11:48,220
something that is like outside of the size of our tree.

154
00:11:48,230 --> 00:11:57,500
So I'm going to say, if size is less than or equal to K, then just return zero.

155
00:12:00,050 --> 00:12:06,290
All right, and then I'm going to actually make another note, neutrinos, just to make this simple

156
00:12:07,220 --> 00:12:08,660
and not too confusing.

157
00:12:09,920 --> 00:12:14,780
And I'm going to call that case more, and I'm going to set it equal to the recursive call of the private

158
00:12:14,990 --> 00:12:15,530
function.

159
00:12:15,550 --> 00:12:21,800
So this will be Kafe smallest where I'm passing the initial route it will start at and then I'm passing

160
00:12:21,800 --> 00:12:25,820
the value k that the user called this function with.

161
00:12:27,080 --> 00:12:31,370
And then what I'm going to do since this returns, an integer is just get the data from that node that

162
00:12:31,880 --> 00:12:33,370
contains the data that we want.

163
00:12:33,380 --> 00:12:37,580
So I'm going to return case more data from this function.

164
00:12:40,150 --> 00:12:46,870
OK, so now let's do the private function for it, so it's going to return the node that we're interested

165
00:12:46,870 --> 00:12:49,750
in that contains the data that the users are looking for.

166
00:12:50,770 --> 00:12:52,930
So let's do that.

167
00:12:54,630 --> 00:13:01,020
And I talked about that initial base case where we need to check if node is null.

168
00:13:02,340 --> 00:13:07,290
So that's like we're at a leaf node and we go off a leaf node in our initial no territory.

169
00:13:07,290 --> 00:13:12,420
So if it's another pointer, then I'm just we're just going to return that null pointer like we talked

170
00:13:12,420 --> 00:13:12,750
about.

171
00:13:13,740 --> 00:13:20,490
So our eternal pointer there and then what we're going to want to do is do the left call and what I'm

172
00:13:20,490 --> 00:13:27,630
going to do is actually save that left call so we can check whether it's equal to null pointer or not,

173
00:13:27,630 --> 00:13:32,730
because remember how we were just returning null pointer and in the recursive process, I kind of just

174
00:13:32,730 --> 00:13:38,610
cascaded like up the tree here, like, oh, we hit no, we hit null and it returns up here.

175
00:13:39,030 --> 00:13:44,400
And then when we found the thing that we were interested in, we wanted to return that and that got

176
00:13:44,400 --> 00:13:46,200
returned up and that wasn't null.

177
00:13:46,200 --> 00:13:52,710
So let's go ahead and put some logic in there to see whether we've hit something null.

178
00:13:52,710 --> 00:13:59,160
And if it is null pointer, then we need to have something like this where we can actually save it here.

179
00:13:59,160 --> 00:14:08,370
So I'm going to say Tree A. Answer equals Cave's smallest, where I'm doing the left some tree call

180
00:14:09,510 --> 00:14:11,540
and so do that.

181
00:14:11,550 --> 00:14:15,780
And then the current case value that we're on.

182
00:14:16,500 --> 00:14:17,540
And then I'll check right away.

183
00:14:17,550 --> 00:14:26,010
I say if the answer is not equal to null pointer, then we're going to go ahead and just return that

184
00:14:26,010 --> 00:14:26,310
node.

185
00:14:26,760 --> 00:14:31,680
So return answer now we're at our processing part.

186
00:14:31,890 --> 00:14:34,950
So we're going to do that, Keith minus minus.

187
00:14:37,210 --> 00:14:38,780
And then we want to do that check.

188
00:14:38,830 --> 00:14:45,820
So if you remember what we were going through in our tree, it's kind of like we processed it when I

189
00:14:45,820 --> 00:14:49,840
put the yellow ring and then we did the subtraction and then I check, is K0.

190
00:14:49,840 --> 00:14:51,310
If so, return the node.

191
00:14:51,320 --> 00:14:52,960
So let's go ahead and do that.

192
00:14:53,530 --> 00:14:59,230
If K equals zero, let's go ahead and return node

193
00:15:02,290 --> 00:15:05,260
and then if not, we're going to go ahead and do the right recursion.

194
00:15:05,260 --> 00:15:08,500
So I will say return cake smallest.

195
00:15:09,130 --> 00:15:16,120
And we will do node right sub tree and test case, of course.

196
00:15:17,670 --> 00:15:22,230
All right, so that should be all our algorithm needs to function.

197
00:15:23,540 --> 00:15:32,780
Let me head back over to our main file, actually, and let's just make a little bit of rain, a little

198
00:15:32,780 --> 00:15:37,700
bit of code for this, so I'm going to just see out, Oh, I already have it there, actually.

199
00:15:37,940 --> 00:15:38,330
Yeah.

200
00:15:38,570 --> 00:15:40,760
So I put that before the lecture.

201
00:15:40,760 --> 00:15:43,280
So that works out nicely.

202
00:15:44,510 --> 00:15:49,610
So we have our fifth statement here and our the smallest value to be found.

203
00:15:50,330 --> 00:15:58,730
Then we are going to read into this as integer that we are already defined up here and then we will

204
00:15:58,730 --> 00:16:04,160
call our case smallest public facing function here, which is this one.

205
00:16:04,640 --> 00:16:06,170
We're passing the integer OK.

206
00:16:06,710 --> 00:16:13,910
It calls this other function with root that finds the correct node that contains the data we want.

207
00:16:15,970 --> 00:16:17,950
And then we just returned the data from this function.

208
00:16:19,120 --> 00:16:28,360
So I have that right here and then I have an input file here that reflects our tree that we had in this

209
00:16:28,360 --> 00:16:29,160
example here.

210
00:16:30,480 --> 00:16:32,730
So let's go ahead and test it out.

211
00:16:33,000 --> 00:16:37,620
Hopefully, everything works, OK, so I'm going to go ahead and run it.

212
00:16:40,780 --> 00:16:45,330
All right, so that they are in order to it's asking us for a value to be found with our fine functionality

213
00:16:45,340 --> 00:16:47,680
and say, well, it found it.

214
00:16:47,710 --> 00:16:49,990
Now let's enter a cave smallest value to be found.

215
00:16:50,210 --> 00:16:51,460
Let's just do our example.

216
00:16:52,300 --> 00:16:54,850
We had the fifth largest value and that ended up being eight.

217
00:16:55,330 --> 00:16:56,680
So let's confirm that.

218
00:16:57,370 --> 00:17:01,960
I'll type in five and we got eight as our fifth largest value.

219
00:17:02,140 --> 00:17:03,910
Let's try something else just to confirm.

220
00:17:03,970 --> 00:17:09,910
So if we look back at our example, what about like instead of the fifth, we do the fourth.

221
00:17:10,480 --> 00:17:11,860
So that should be seven.

222
00:17:12,310 --> 00:17:17,350
And then maybe I'll do the let's see second or something like that.

223
00:17:18,070 --> 00:17:19,300
Let's try it multiple times.

224
00:17:19,330 --> 00:17:25,810
So let's go ahead and do the seventh largest value or sorry, not seventh largest seven will be the

225
00:17:25,810 --> 00:17:27,520
largest value, but we'll do the fourth.

226
00:17:28,750 --> 00:17:30,950
OK, so that is seven, in fact.

227
00:17:31,840 --> 00:17:33,430
So that worked out.

228
00:17:34,270 --> 00:17:38,350
Let me read it one more time, and I'll just do the second largest value.

229
00:17:41,920 --> 00:17:46,060
And that was five, so for starting here three is our first artist.

230
00:17:46,450 --> 00:17:48,580
Five is our second largest.

231
00:17:49,030 --> 00:17:51,400
So that worked out OK.

232
00:17:52,810 --> 00:17:53,170
All right.

233
00:17:53,290 --> 00:17:59,860
So hopefully that was enough of an explanation for you to understand this function and definitely congratulations

234
00:17:59,860 --> 00:18:02,060
if you were able to figure this out on your own.

235
00:18:02,080 --> 00:18:06,030
And if you use a different method, then that's totally fine.

236
00:18:06,040 --> 00:18:09,160
Maybe you added stuff to a vector or something like that?

237
00:18:09,670 --> 00:18:11,620
Um, doing it in order traversal.

238
00:18:12,670 --> 00:18:17,770
But then we offer this lecture and I will see you in the next one.