Hi, everyone, welcome back.
So in this video, we are going to discuss about this question gets my smallest element in about.
So we are provided with the best given about input and our as input.
Right about and have a look.
So we need to find out the key at smallest element in a best.
For example, if the value of KS one, the smallest element will be one.
So my answer should be one.
If the value of KS two, then this element is the second smallest element to my answer should be to.
Let's take one more example.
So let's talk about this one.
So here, if the value of K is, let's say four, I want to find out the fourth smallest element.
So this is the first smallest.
This is the second smallest.
This is the third smallest.
And this is the fourth smallest.
Samantha should be for this node.
So we want to return integer.
So I will not return this compute node.
I will return.
So my answer will be forward.
And if the value of K Street, then this is the third smallest element surmounts I should be three.
So I hope you haven't answered the question that it's very simple.
BSD is provided to us the value of KS provided to us, and we need to find out the smallest element.
And we want to return that element to a very simple solution.
Can be.
We know that if you are provided with the best and if you do in order traversal so traversal of BSG
is basically sorted so we know how to do in traversal.
So what will do?
We will maintain one, Eddie.
They will maintain one at and we will insert all the data in the area.
So I am doing traversal.
So first of all, I am going to visit this node, so I will insert one, then I will visit this.
So I will answer to then I will visit this, I will insert three, then four, then five and then six
and so on.
So basically, when we are doing traversal, we will store the data in this area.
So this area will obviously be assaulted.
So when you're performing in order to store all the data in the area and the area will be a certain
area.
Now, you have a certain area basically, and you have the lucky.
So what you will do, you will simply find out, for example, if the value of case one, they should
be the first value.
So in the area, the indexing starts from zero.
So your answer will be, if this is your area, then your answer will be array of key minus one.
You want to find out the third smallest element.
So add a second index.
The third smallest element is present.
So this will be your answer, three minus one.
So what will be the time and the space complexity of this approach?
So time complexities unit to insert into doing traversal and you will insert all the elements in the
eddy, the time complexities big off and Veronese, the total number of nodes present and similarly
what the be complexity.
So you need to create this area and this area will contain all the nodes of the Chinese history and
the number of nodes that.
And so this is the time and space complexity of this approach.
Now, one more approach can be so you are doing in a reversal rate, you are doing in order traversal.
Let's just maintain one more variable when you are doing in order to that is the variable count.
So what this current variable will do.
So first of all, we are going to visit this node.
So the value of current will become one.
Then we will visit this node.
So the value of count will become two.
I am talking about in order traversal, then I will visit this node.
So the value of current will become three here, here, the value of currently before here, the value
of currently five here.
The value of current will be six and will do so as soon as the value of count become Miklaszewski,
we will stop.
So for example, if the value of Kastari so here the current will become three made what we are doing,
we are simply doing countless plus for every node.
So here I will look.
Initial level of count will be zero.
So I will look Kadal become then I will look on a split second that comes to I will do current plus
the count will become three and three is close to case.
So I will stop here.
I will stop and my answer will be this data.
Simple right.
So what to do.
Just write one helper function.
That helper function.
But it will take, it will take you in order.
It will take the current variable.
And what else?
And it will take your answer.
So in this case, my answer is three.
So when you are stopping what you will do, you will update your answer that your answer is no.
Your answer is No.
Three.
And obviously what will happen.
So this function will call this helper function.
So you need to pass these two variables by reference because I will return the value of answer from
dysfunction.
So I need to pass on several Bio-Reference so that the changes that you are doing here should be reflected
in this main function.
So if you will follow this approach, what they are doing, you are doing in order traversal Magoffin,
but you will not create any extra space.
You will not create any Eddie, since you will use recursion.
And if your tree is like this, that is your tree is as good tree.
So what will happen?
Basically, all these values will be present in this track.
And since all the nodes will be presenting in this taken the worst case.
So time and space complexity still big often and big often.
So we are not improving upon this piece, but we are improving that.
We will not use any we will not use will not need to create another array to solve this problem.
So we are improving space complexity.
Right.
So, yep, you can write the code for the helper function, just perform the.
So this is not in order.
You will take preassembled, it will take three years input and they will perform the write the code
for the traversal and plus if the count becomes equals 2k you know the answer and you will stop.
So the court is going to be very, very simple, in fact, it's so simple that you just need to write
in order traversal court and a little bit of modifications.
So we will be writing the code in the next video.
And I will see you there.
Thank you.