Hello all and welcome back.
So in this video let us continue our discussion on Bsts.
And now let us try to solve a question.
So the question is given a array or a list which is sorted, we have to convert that into a BST.
Now in the start of this module I explained you that how bsts are a lot inspired by binary search and
how when we see the inorder of a particular BST, it is a sorted array.
So this question will help us to understand that how if we are given a particular sorted list or array
that can be made into a bsts.
Okay, so let's see the same.
Everyone now assume that we are given a array, a sorted array or list, which is something like this.
And seven now one BST, which we can very well make from.
This is something where we take one here and then we take two.
And going forward like this, of course we are adding seven in the end.
Now though, it's the right side, like there is nothing wrong in this particular thing.
It's a skewed BST.
And again, I will not be able to do any operation on this particular tree in a very optimized manner
because it's as good as a linked list where I will have to go to each and every node.
In the last question, we saw that how searching in a BST is very helpful, right?
Because I can just get rid of half of my tree either I used to go on the left half or the right half
something which we use, which we loved in Binary Tree, because that used to actually help us in tackling
the problem of complexity.
Right.
So we have seen that how big of login is a lot better than big O of N.
So on the same understanding we should try to create a balanced BST.
Okay.
So we will be trying to create a balanced BST though the right one is also a BST and it's a created
from the sorted array only.
Our aim here is to create a balanced BST.
Now for that, if we have to create something which is balanced, that means we have to ensure that
the left and the right half are getting equal distribution of elements.
That is what balanced is.
For that, I think the obvious thing to do is to pick up mid.
Okay.
So the operations will be pick mid.
And start.
By creating eight nodes creating its node creating its node.
So the very first element which I'm going to pick is four because that ensures that there is a balanced
distribution of element.
Then I think if I'm able to just ask the person to give me the left half and the right half, because
now again, I have just made my problem smaller.
So one, two three and five six, seven.
Right, everyone?
So I've just made my problem smaller and I can ask recursion.
Once I have created this particular node which is going to be four.
Then let us just say that recursion is going to help us in forming these left and the right subtree.
I will be passing one, two, three here and I will be passing five, six, seven here.
Great.
So I hope the overall idea about the question is clear.
Everyone.
Now let us quickly code the same as well in VS code.
So this is the file which I have created.
So it is sorted array to BST.
Now first let us just get the print function.
So I'm importing from this particular file print bst function.
We have to create a If a function so sorted list to BST.
And let's say I am getting the list in L1.
Great.
So for the time being, let us make it fast and see what exactly can we get.
So I have to return a root.
So I will be getting the root from this particular function where I can pass a list like this.
Okay.
So it's a sorted list right.
Now what I have to do.
I can just print this as well.
Right.
In this particular function first let us see okay.
If length of L1 equals zero.
If you are sending me an empty list okay, then I cannot do anything right.
I cannot do anything.
I should just return none, which is an empty node.
We can actually solve it by using start and end points as well.
Just for this case, I'm using the slicing concept.
I will suggest that you can just solve.
Try to solve it using the start and end indexes as well, because in that the overall condition used
to become.
If start is greater than end.
Right now I'm going to find the mid mid element.
It's going to be length of L1 flow division two okay.
So middle finding the middle index.
Then I can say route data is something which is L1 of mid.
I have the route data with me now and I can create my route, which is going to be we will have to get
the best node as well.
Everyone.
So is it present here.
Yeah.
So just let us get this binary tree node.
Binary tree node okay.
Or what we can do is let us copy this and make this a BST node.
that will also do.
Okay, great.
So BSD node right.
So BSD node.
And we just have to pass the root data.
Great.
Once I have created the root I have to return this root only.
That is fine I can return root.
But before returning what exactly I have to do.
Root dot left equals sorted list to BSD.
And now I should pass just the first half.
So I should just pass one two, three.
How can I say that it will be equal to L1 of all till mid and root dot right is going to be equal to
sorted list to bst L1 of mid plus one.
Because I have taken mid already to the end and I feel that it should give me my BST.
Okay, so I hope the overall function is clear.
Everyone.
It's along the lines.
The one which we have been coding.
So let us now write.
Just try to run this once and I see that overall I am getting this sorted only so we can assume that
it should have run fine.
What we can also do is let's say take this particular print function, the one which we write like this,
right where it tells us the root and all the children and copy it here.
And let us use this function to see if the four actually have been created as a node.
So let us print like this okay.
Great.
Everything we have seen already four left, two right six then one.
So it seems like it has been divided nicely.
Four it would have been two, then six, then one, three and five, seven.
So four, two and six, two, one, three and six, five and seven.
So it seems like everything is fine.
Okay.
We are able to create our list into that.
Now, one thing which I have to now ask all of you is that what if someone gives something like, uh,
let's say five year again?
Or let's say someone gives zero here, okay.
It's not sorted altogether.
Our current code is going to make it right.
It's going to actually make the same thing.
But I believe that we should have some function or some way we can check if this is actually BST or
not.
Right, everyone.
So if something which we have created or if we are getting something, yes, it is still using the best
node.
That is the understanding.
But till now we have not written function to check if a particular code is a particular tree which is
given to me if it's a BST or not.
Okay, so in the next video, we are now going to see what are the best ways through which we can check
if the given root if the given node is a BST or not.
So meanwhile, I will expect all of you to think a little bit on that, and we will discuss the approach
for the same in the next video.
Thank you.