OK, so going back to a another lecture on binary search trees.
In this lecture, we are going to go over the theoretical and actual implementation, part of a another
specific function for binary searches, another algorithm and that is going to be the function that
finds the K the smallest value in the binary search tree.
And so this is a pretty popular algorithm to be asked in interviews or, you know, so as far as I've
heard.
And so that's why I wanted to cover it since we're kind of going over a limited amount of functions
with binary search trees other than the basics.
So basically, it's just like it sounds the user or the client file would ask for.
They provide a number and that number or integer, if you will, will be the case value for the K,
the smallest value in the binary search tree in which we will need to return.
Hmm.
And so I definitely invite you to pause the video or stop now and take your time and see if you can
solve this on your own.
I did not include it as an exercise because in my opinion, this is one of the harder binary search
tree algorithms.
Some people may not agree with me, but I found it to be a little bit more difficult than the other
ones.
I'm not really sure why, but definitely made me want to cover it.
So if you want to figure this out, go ahead and post the video and see if you can solve this on your
own.
Otherwise I will walk through it.
OK.
So of course, congratulations if you were able to figure it out.
Of course, a lot of there's, you know, different ways to do this.
I won't say a lot of different ways.
But the main idea is going to be that since we are looking for the smallest, we kind of want to start
at the smallest and go up from there.
And when you think about that, it's kind of like something being sorted in order.
And we already have discussed a method of traversing this tree in order, and that is in order traversal.
And if you recall correctly, that involves us going all the way to the left first to get to the smallest
value and then kind of doing our thing, which would be like processing the node and then going to the
right.
And if we recall correctly, that is how the tree is kind of organized.
It's organized like the left.
It's basically like, you know, if you're going to give a no, let's say five, you know, the left
is smaller and then comes five and then comes the right.
So it's like left middle, right kind of.
And that is the in order to wrestle.
So it would be a good idea for us to try and use the idea of in order traversal to solve this problem.
And that's exactly what we're going to do.
And now a solution might involve doing it in order traversal and then just kind of appending to another
container, which is that great idea if that's how you ended up doing it.
If you attempted this on your own and you can kind of go left some tree call and then add it to a vector
or something and write some tree call, you know, that might work out if that is, you know, another
way that you like to do it.
I'm just going to go over the just straight up recursive function that will return in the case smallest
without using another data structure besides just traversing the tree itself.
So that's how I'm going to do this.
So let's go ahead and get started, I have an example here where Kaye starts out as five, so that means
the user passed five to the function and I have this condition here because this is an important condition.
We're going to use a strategy of subtracting from the value that the user has passed.
And then once we reach zero, we are going to return the node because we will know that we are at the
node with the answer.
And so I'm going to set it up in a way where we can do it in order traversal.
And we're going to do that like left call and then processing in which we will do the subtraction and
then we will do the right call.
So that's an order style reversal.
And we will want a check.
Before we do the right call, we will want a check to see if K is zero, and in that case, we know
we've gotten to our answer and we will then return that node and that node will have the value assets
data member that we will want to return to the client.
All right, so let's go ahead and walk through this example.
So if we were going to do that in order to wrestle, we'd want to go left all the way first.
So we'd start at the route and we go to seven, five three and all the way down to no.
We're going to want another probably a primary base case.
As you know, if we reach no.
We're going to want to just return that no back.
So we don't have any problems there and we'll know that we're at a leaf node.
So let's just assume that.
So we're going to do recursion coming back from this novel because we've regional and it's a base case.
So we return that.
And then since we've returned that and we went left, you can imagine that we're coming back to our
left recursion call here at this node.
And so if we're doing that in order to wrestle, we are then going to want to process this node.
So I'm going to note that with this yellow ring here, so we're processing the node, and since we're
processing it, we're going to subtract.
So we're going to subtract one.
We'll do a K minus minus, and that'll bring us from five to four.
And so then we want to check, you know, is K zero, no, K is not a zero, it's four.
So let's go ahead and do our right recursion then.
So we hit no down here for our right recursion, and then we'll have that initial base case where we're
returning null.
If we encounter no, we're going to return it back.
So we do that and we return now back to here.
And now that we've processed both of these, we're going to go ahead and return back up to here because
we've done like a fall in order to kind of to of this zone right here the submarine.
And so you can notice that since we're coming back up here, we just finished a little left sabiri call
from this stack, frame this node.
And so we're going to move to that next part, which is processing.
So we're going to go ahead and process this node and we will subtract and we'll check again as K0 Care's
not zero.
So let's go ahead and do the right recursion.
So we do the right recursion.
We come here.
Then once we do our right recursion, you know what we're going to do, and I want to note is we still
going to follow that left first, then process, then right.
So we're going to go left and that's going to be null.
And so we will return back with that null from our initial base case, which is going to be if we're
at no and we're going to return null, then we'll do our processing.
So let's do another minus minus two.
Now check K is two, it's not zero.
So it's to our right recursion.
We hit no again.
So we return back.
We've processed both of these.
So we were going to return back up to here again, which is still that null.
You know, we can't return nil.
Return nil again.
Return back up to here.
And then now we've processed the left and right for this, so we're going to return back up to here
and now, if you're thinking about the function again, kind of like pseudocode in your head.
Remember once again that now we're coming from this left sub trickle of this stack frame.
And we've gotten A..
So we're going to then go to the next part since we've done the left call and we're going to process
this.
And then we're going to do a subtraction again.
So now we're at one one is not zero, so let's go ahead and do the right.
So we go to the right, then we can do that whole thing over again.
You know where we have to go to the left first and then process and then go to the right.
So we go to the left first from here and then it's null.
So we return that no backup.
Let's go ahead and process, we process it so that we're going to do the subtraction as part as our
processing the known.
Check is K zero, K is zero, so we're not going to do the right recursive call now, we're just going
to return node, so let's return the node back up to here and we return to the node up to here.
And you notice that this has had the left subtropical completed and its tenants rights have to be called
completed.
So this return node comes back up to here and the function is done, and so it's going to return back
up to here.
And so while now we have our answer, eight was the fifth smallest value in our tree.
So one two three four five fifth smallest value.
OK, so hopefully that explain it theoretically enough.
Let's go ahead and implement this thing in code.
So I'm going to head over to Sea Lion.
I've already had it pulled out and unclear this.
I'm in the header file of our binary search, B, T H, and I'm going to go ahead and put just like
we've been doing before, I'm going to have a public facing method and a private one.
So let's make the public function here where we get the integer K from the user.
So that is just going to return an integer because we'll want to return the actual K the smallest.
And so I'm going to call it case smallest, and it's going to take that integer from the user K.
Then I'll make the private one here, and it's going to turn the node that has the data we're looking
for.
So that's going to be a trainload pointer also going to call it K smallest and then it's going to basically
recursively need to pass the sub trees, which will be like a node.
And so that's going to have a tree node pointer node is what I'm going to call it.
And then we're going to have our, of course, our integer K and that's going to be passed by reference
and we're going to be updating K and passing it recursively.
So I have both these functions, the private and the public version of it for our client file.
And I'm going to head over to the BPP file to implement this, so let's start off with that public facing
one to the scope or solution there.
Do care the smallest and the first thing I'm going to do is make sure that the user's not asking for
something that is like outside of the size of our tree.
So I'm going to say, if size is less than or equal to K, then just return zero.
All right, and then I'm going to actually make another note, neutrinos, just to make this simple
and not too confusing.
And I'm going to call that case more, and I'm going to set it equal to the recursive call of the private
function.
So this will be Kafe smallest where I'm passing the initial route it will start at and then I'm passing
the value k that the user called this function with.
And then what I'm going to do since this returns, an integer is just get the data from that node that
contains the data that we want.
So I'm going to return case more data from this function.
OK, so now let's do the private function for it, so it's going to return the node that we're interested
in that contains the data that the users are looking for.
So let's do that.
And I talked about that initial base case where we need to check if node is null.
So that's like we're at a leaf node and we go off a leaf node in our initial no territory.
So if it's another pointer, then I'm just we're just going to return that null pointer like we talked
about.
So our eternal pointer there and then what we're going to want to do is do the left call and what I'm
going to do is actually save that left call so we can check whether it's equal to null pointer or not,
because remember how we were just returning null pointer and in the recursive process, I kind of just
cascaded like up the tree here, like, oh, we hit no, we hit null and it returns up here.
And then when we found the thing that we were interested in, we wanted to return that and that got
returned up and that wasn't null.
So let's go ahead and put some logic in there to see whether we've hit something null.
And if it is null pointer, then we need to have something like this where we can actually save it here.
So I'm going to say Tree A. Answer equals Cave's smallest, where I'm doing the left some tree call
and so do that.
And then the current case value that we're on.
And then I'll check right away.
I say if the answer is not equal to null pointer, then we're going to go ahead and just return that
node.
So return answer now we're at our processing part.
So we're going to do that, Keith minus minus.
And then we want to do that check.
So if you remember what we were going through in our tree, it's kind of like we processed it when I
put the yellow ring and then we did the subtraction and then I check, is K0.
If so, return the node.
So let's go ahead and do that.
If K equals zero, let's go ahead and return node
and then if not, we're going to go ahead and do the right recursion.
So I will say return cake smallest.
And we will do node right sub tree and test case, of course.
All right, so that should be all our algorithm needs to function.
Let me head back over to our main file, actually, and let's just make a little bit of rain, a little
bit of code for this, so I'm going to just see out, Oh, I already have it there, actually.
Yeah.
So I put that before the lecture.
So that works out nicely.
So we have our fifth statement here and our the smallest value to be found.
Then we are going to read into this as integer that we are already defined up here and then we will
call our case smallest public facing function here, which is this one.
We're passing the integer OK.
It calls this other function with root that finds the correct node that contains the data we want.
And then we just returned the data from this function.
So I have that right here and then I have an input file here that reflects our tree that we had in this
example here.
So let's go ahead and test it out.
Hopefully, everything works, OK, so I'm going to go ahead and run it.
All right, so that they are in order to it's asking us for a value to be found with our fine functionality
and say, well, it found it.
Now let's enter a cave smallest value to be found.
Let's just do our example.
We had the fifth largest value and that ended up being eight.
So let's confirm that.
I'll type in five and we got eight as our fifth largest value.
Let's try something else just to confirm.
So if we look back at our example, what about like instead of the fifth, we do the fourth.
So that should be seven.
And then maybe I'll do the let's see second or something like that.
Let's try it multiple times.
So let's go ahead and do the seventh largest value or sorry, not seventh largest seven will be the
largest value, but we'll do the fourth.
OK, so that is seven, in fact.
So that worked out.
Let me read it one more time, and I'll just do the second largest value.
And that was five, so for starting here three is our first artist.
Five is our second largest.
So that worked out OK.
All right.
So hopefully that was enough of an explanation for you to understand this function and definitely congratulations
if you were able to figure this out on your own.
And if you use a different method, then that's totally fine.
Maybe you added stuff to a vector or something like that?
Um, doing it in order traversal.
But then we offer this lecture and I will see you in the next one.