Hello all and welcome back.
So in this video let us now continue our discussion on Bsts.
And now let us try to solve another question.
So the question is print elements in a range.
In this question we will be given a BST and a range okay.
So let us take an example.
Let's say our BST is something like this.
So taking it as a normal balanced BST which we have been taking.
And along with this I will be giving a range.
So for example, let's say in this particular case it is something like this.
Okay.
Now what effectively I have to do, I have to print each and every element which falls between this
range.
Okay.
The same would be doable in normal binary tree as well.
We just have to make sure that we go to each and every node.
But because of the property of Bsts, where the left I know is always going to be smaller than my root
node value and right subtree, everything is going to be bigger than my root node value.
I can do some optimization here.
Okay, so what can be the optimization?
Let us take some examples.
First, let's say that I am given the range which is something like this.
So the range is from say 15 to 45 okay.
Now when I will be comparing this 1545 with my root which is this 50.
Do you think we should call to this right subtree as well to find this particular element in this range?
I do not think that should be done right, because 45 is even smaller than 50.
And I know that everything going forward is going to be greater, right?
In a similar manner, the one which is given that is 55 and 75, let's say in this, I don't think I
need to call on the left part because 55 is bigger than 50.
I know everything else is going to be smaller than my 50, right?
So here what can I do as a overall optimization is that at each and every point, I can compare with
my root value.
If it lies within overall low and high value, then I can print it.
But if one of the overall boundary is not met, for example here 55 and 50, then I can optimize on
making that call.
Okay.
So let us quickly code this everyone.
Let us have a new file.
Print in range dot p y.
So def let's say print best in range.
Okay.
I will be getting a root.
I will be getting a low and say I'm getting a high.
Okay.
So low and high value.
Base case.
If my root is none, I can return as it is, I cannot print anything, right?
Second, if my low is less than root dot data, then only I have to make the call in the left side.
So what is it saying?
That low this 50.
Is it less than this particular thing?
Root dot data?
If yes, then we can make the call here.
Right.
Because from 15 it can happen that it will basically be there.
Okay.
So let us make that call.
Print range root dot left and low and high right.
Now I have gone to left.
I should check if low less than equal to.
So we can take the equal to towards the right side.
That will be better.
Like if in case we want to take the equal to value as well.
High.
Okay.
Or rather we will have to make sure that it is this as well.
Because if it is equal to either low or high then I should print this route data.
Okay.
So I hope this is clear.
If it is on the boundary then we are printing it.
After that.
The last check I have to get is if high.
If it's greater than route dot data.
Okay then only I have to make a call to the right.
So which case is this?
If high is greater than route dot data.
So let's say here 75.
It's greater than my 50.
So I will be making the call.
But here my high 45.
It's smaller than the route data.
So I will not make call on the right side.
So this is some optimization which we can do.
Let us quickly check this out.
So from predefined import.
Second.
Yeah.
So we already have created these trees right.
With us we have these trees.
Route one.
Route two.
Route three.
Let us have them.
And for route three which is this one, let us try to have for 25 and say 50.
Okay.
So let us try to print it like this.
So print BST in range route 325 and say 50.
And let us run this and we are able to see these elements.
Okay.
So they are sorted.
The reason is that I called on left first, then I worked on myself and then on the right.
So it's kind of an inorder way of doing these things right.
So let us see if it is 25.
Yes 30 then 20 is not there.
Of course 35 is also there, 40 and 50.
Right.
So it seems to work fine.
Uh, maybe what we can do is 125 and 150 and nothing is getting printed.
Okay, so 25 to 150.
I think everything should get printed, right.
Lots of elements.
So all the way from this 25, all these elements will get printed as we are able to see.
So it seems like this is working fine.
Okay.
So yeah, I hope that's the question.
Uh, just the idea is that because we have the property, we have to see that where all that can be
applied.
Okay.
So we have the knowledge about the property.
We have to do something.
We just have to now see where exactly can this overall idea of low to high can be applied.
Okay.
So cool everyone let's meet in the next video where I will be telling you based on kind of this intuition
which we get from this question, how can we also find out if our tree is a binary tree a BST or not?
Okay.
So do make sure that you practice.
And this overall concept is clear.