Welcome back.
In this video, let's think about how we can solve this question.
First let's go ahead and create a binary search tree which is valid now for the root node.
Let me have any value which is ten.
Now we can notice that if we have any value over here, which is between minus infinity and infinity,
that means any value, right?
Then also our binary search tree would be valid.
So let me write the limits over here so I can have any value over here which is between minus infinity
and infinity.
Now let's say I want to insert a node to the left of this particular node.
So for example I can insert the value five over here.
Now any value which I insert over here will be valid if it is between negative infinity and ten, because
the value towards the left of this particular node has to be strictly less than ten, right?
So the limits for the value which I can have over here is minus infinity and ten.
So I can say minus infinity less than the value and then less than ten.
So over here we have five.
Now this is satisfied.
That's why this is valid.
Now let's say I want to insert something to the right over here for this particular node.
So what would be the limit.
Now I just need something greater than ten right.
So for example let me insert the node with value 20 over here.
Now let's think about the bounds.
Now if I want to insert any value over here now 20 is a valid case.
Now what would I be thinking about.
Right.
So what is the limits that I'm thinking about.
I should have something which is greater than ten.
And then it has to be just less than infinity, which means that it can be anything.
So it can be 200, 2000 or 20,000.
So I can say that the limits for whatever I'm putting over here is ten less than 20 less than infinity.
Now let's go ahead.
Let's try to insert something to the left of this particular node over here again, because it's towards
the left of this node, we know that it has to be less than the value five over here.
So for example I can take the value three.
Now again what are the limits for any value that I want to insert over here.
Any value which satisfies which is less than five right will be valid over here.
So I can say it just has to be greater than negative infinity, which means that it can be anything,
but it has to be less than five.
All right.
So that's the range for values that are possible for this node over here.
Now let's try to insert something to the right of this particular node.
In that case it becomes interesting right.
It has to be greater than five.
But because it's towards the left of ten it still has to be less than ten.
So what is a possible value.
Let's say seven seven is a possible value.
So I can have seven over here.
Now to generalize the limits for what value can come over here.
It has to be greater than five but less than ten.
So I can say five less than seven less than ten and seven is the value that we have just chosen.
So anything which is between 5 and 10 would have worked over here.
Now let's go ahead and insert something to the left of this particular node over here.
For example I can have 15 right.
So it just has to be greater than 1010 which is this node over here because it's towards the right of
ten.
But it has to be less than 20.
So it has to be in between 10 and 20.
So for example 15 works.
Now the limits to generalize for what can come over here would be ten less than 15 less than 20.
Similarly, let's insert something to the right of this particular node over here.
For example I can have 30.
Now the condition for this is just that it has to be greater than 20, right.
So it has to be greater than 20.
And I can say it can be less than infinity, which means it can go as high as it wants.
So we have 30 over here.
Now let's continue.
Let's try to insert something over here.
So let's say we have four.
So again over here the condition is interesting.
It has to be greater than ten right.
And so sorry it has to be less than ten because it's towards the left of ten.
And it has to be less than five because it's towards the left of five.
Right.
But it has to be greater than three.
So we can say that the limits are between 3 and 5 over here.
So it has to be greater than three but less than five.
So I can say whatever value I insert over here has to be in between 3 and 5 and four satisfies that.
Now let's go ahead and insert something over here.
So let's say I want to insert to the left of this particular node to the right of this particular node.
All right.
So let's take right in this case.
Now, if I want to insert something to the right of this 15 over here, it has to be greater than 15.
But because it's part of the left of 20, it has to be less than 20.
Right.
So 17 works.
So let's try 17.
Now to generalize the condition is that it has to be between 15 and 20.
So we have 15 less than 17 less than 20.
Similarly I can insert 18 over here right.
So I can have 18.
So what's the criteria for this.
For 18 it has to be greater than whatever we have over here which is 17 right.
It has to be greater than 17 but it has to be less than 20, which is what we have over here.
So I can say 17 less than 18, less than 20.
All right.
So we have just seen how we construct a valid binary search tree.
So what is the thinking that would go on in our head when we go ahead and construct a valid binary search
tree.
Now let's try to look at a pattern which is there over here so that we can use it to solve the question.
Now we started with ten and we have seen that any value is fine at the root.
Now when we wanted to insert something to the left of this node, right.
So when we travel towards the left, you can see that we changed the maximum value over here it was
infinity.
We changed that to the previous value which was ten.
Again, when we move towards the left right.
Towards the left you can see we get we are again changing the maximum value from 10 to 5.
Now when we move towards the right towards this direction, let's say we start again from ten.
When we move towards the right, you can see that we are changing the minimum value.
Over here the minimum was minus infinity.
But when we move towards the right that changed to ten again.
When we move in the direction that is towards the right, we are changing the minimum value which is
20.
So from ten we are changing it to 20 which is this value over here.
So this is the interesting pattern which we will use to solve this question.
Again you can notice over here.
From here we have this criteria.
When we move towards the right we are changing the minimum value again from minus infinity to five over
here.
So whenever we are moving towards the left we are changing the maximum value.
And whenever we are moving towards the right, we are changing the minimum value for the value of that
particular node to be valid, such that the given binary tree is a binary search tree.
So this is how we are going to solve this question.
All right.
So we will have a recursive function and we start at the root node.
So when we are at the node we will check whether it's between the bounds.
And initially we will just say that the value for the root node has to be between minus infinity and
infinity, so that any value is fine at the root node.
Then we will have a call and to check whether its left subtree, which is this part over here is a valid
binary search tree.
And we will have a call to check whether its right subtree, which is this tree over here is a valid
binary search tree.
Now if these two are valid binary search trees, then we will return true and if not we will return
false.
So this is how we will do it right?
So it's going to be a recursive call.
So let's just see the recursion happening.
So first we start at this node over here.
And then to check whether its left subtree is a valid binary search tree we will move in this direction.
So when we reach this node we will check whether the value for this node is in between the range minus
infinity to ten.
Right.
So for this we are just changing the max value from infinity, which was the previous upper limit to
this value over here which is ten.
So again we get the limits minus infinity and ten.
And we will check whether the value over here is in between these bounds.
Now if that is not the case then we would just return false because we have identified that the tree
would not be a valid binary search tree.
But if it is true, we will proceed and check whether its left subtree and its right subtree is a valid
binary search tree or not.
So let's proceed.
So over here we can see it's true.
So to check whether its left subtree is a valid binary search tree, we again move in this direction
which is towards the left and we are changing the maximum value from 10 to 5, which is the value over
here.
Right.
So the range now has to be in between minus infinity and five.
And for this node we check whether the value is in between this range.
We see it's in that range.
So we proceed.
If it was not so we would have just returned false.
Now we are going to check whether its left subtree and whether its right subtree is a valid binary search
tree.
Now the left is nothing over here we just have null.
So we go ahead for the right part.
Now we move in this direction and when we move towards the right, we are going to change the minimum
value right.
So the minimum is minus infinity over here that's going to be changed to this value which is three.
So we have the bounds as three and five for this particular node.
And we are checking whether the value is in that range.
And we see it is it's the case.
So by now we have established that the left subtree of this particular node is a valid binary search
tree.
So we are now going to check whether its right subtree is a valid binary search.
So we reach this node over here and we check whether this node is in the range which is five and ten.
Right.
So how do we get five and ten.
We have minus infinity and ten over here.
And we are moving in the right direction.
So we're going to change the minimum value from minus infinity to five.
So we will get five and ten as the range.
And we see that it's in that range.
So we have by now identified that the left subtree of this particular node right.
So that is this part over here is a valid binary search tree.
So now we will move in the right direction to check whether the right subtree is a valid binary search
tree.
So we go over here.
Now we come to this node.
Now when we move towards the right we will change the minimum.
So the minimum is changed from minus infinity to ten over here.
And we will check whether the value over here in this node is in between ten and infinity.
Now we see that it is.
Yes it is indeed in this range.
So now we are going to check whether its left subtree and whether its right subtree is a valid binary
search tree or not.
So let's proceed to check whether the left subtree of this particular node is a valid binary search
tree.
We move in this direction and we reach this node over here.
Now we are moving left, so when we move left we will change the maximum.
So the maximum over here is infinity.
That's changed to this value which is 20.
So we get that the bounds are ten and 20.
And we're going to check whether the value of this node is in between 10 and 20.
Now if it was not the case we would have just returned false.
But we see that yes it's in that range.
So we proceed and check whether its left subtree and its right subtree are valid binary search trees
or not.
So over here we just have null.
So we proceed to the right part.
So we come to this node.
And when we move towards the right we are going to change the minimum.
So the minimum from ten is changed to 15.
So our range now is between 15 and 20.
And we are checking whether the value at this node is between 15 and 20.
We see that yes that's the case.
So we will check whether its left subtree and its right subtree are valid binary search trees or not.
So towards the left we just have null.
So we go to the right.
And again because we are moving towards the right we will change the minimum.
So from 15 we change the minimum to 17.
So 17 and 20.
So that's the range now.
And we are checking this value.
Is it between 17 and 20.
Yes 18 is between 17 and 20.
So yes we see that this is also true.
The value is true.
It's following the binary search tree property.
So by now we have established that the left subtree of this particular node is a valid binary search
tree.
And hence we are going to move towards the right.
So we come over here.
Now when we move towards the right we are going to change the minimum right.
So ten is now going to be changed to 20.
So we have 20 and infinity as the range.
And then we are going to check whether the value of this node is between 20 and infinity.
And we see that yes that's the case.
So that means by now we have identified that previously we we we've identified that the left subtree
over here was a valid binary search tree.
And by now we have identified that the right subtree for this particular node is a valid binary search
tree.
So this will return true and this will return true.
And then because this and this is true, we will just return true.
Which means that the given binary tree which is given to us is indeed a valid binary search tree.
So this is how we will solve this question.
Now let's take a quick look at the time and space complexity of this solution.
So when it comes to the time complexity, we have to traverse every node, right.
So that's why the time complexity is going to be O of n.
So we have to traverse every node and check whether it is between the particular range which is applicable
for a value in that place.
Right.
So after going to a particular node we're just doing some constant time operations which is checking
whether it is within the bounds.
So that's why the time complexity of this solution is O of n.
And the space complexity of this solution is going to be O of the maximum depth or the height of the
given binary tree.
Right.
Because that's because this is going to be a recursive solution.
And then because we are going to take up space on the call stack.
So that's why the space complexity is O of H.
Now in the worst case this is going to be O of n because that is the case where the binary tree looks
like a linked list, right.
Which is something like this.
Every node is going towards the right for example.
So in this case we have to go all the way down.
So that's why we can say that in the worst case the space complexity is going to be O of n.