Hi everyone, let's do this question.
You are given the root of a binary tree.
Determine if it is a valid binary search tree.
A valid binary search tree is defined as follows.
The left subtree of a node contains only nodes with keys less than the nodes.
Key.
The right subtree of a node contains only nodes with keys greater than the nodes key.
Both the left and right subtrees must also be binary search trees.
So this is a question we are dealing with now.
Again, remember in binary search tree questions, it's important how the binary search tree is defined.
In a previous question, we defined the BST such that the left has to be strictly less, but the right
was greater than or equal to the value of the node.
So that's how we defined the binary search tree in a previous question.
Now over here in this question it's defined that the left has to be strictly less and the right value
has to be greater than strictly greater than the node's key value or the node's value.
So this is important.
All right.
Now again remember what we have to do is we will be given the root of a binary tree.
And we have to check whether it is a valid binary search tree.
So that's the question now in the interview, if you are getting this question always, you have to
ensure that you ask sufficient clarifying questions so that you are very thorough with what the expectation
is.
And you, you have no doubt about any edge case, etc..
Now, a good question that you could ask over here is will there be duplicate values in the binary tree?
So whenever you're dealing with binary search trees, this is going to be a question that is going to
be important.
The case about duplicate values.
Now over here because it's defined in this manner.
That is the left value has to be less than the node's value.
And the right value has to be greater than the node's value.
Therefore, let's say the interview over here replies to you that yes, there can be duplicate values,
but in that case the binary tree is not a valid binary search tree.
All right.
Now let's go ahead and write a few test cases.
Now remember in the interview you can always ask the interviewer if he or she is okay with coming up
with test cases together with you.
So that will help solidify your understanding of the question, and you will be very thorough with what
the expectation is.
That's a good practice.
Now over here, let's go ahead and write a few test cases.
Let's say the binary tree which is given to us is this one over here.
So in this case you can see that we would have to return false because this value over here has to be
less than the value over here.
Right.
Because you can see the left value has to be less than the node's value.
So that was what is mentioned.
And that's the binary search tree property.
So this is clearly false.
Now if the tree with the binary tree which is given to us is this one over here, then also it's going
to be false because this value over here has to be greater than the value which we have over here.
And that's not the case.
Right.
So over here also we have to return false.
Now let's take another case.
Let's say the binary tree which is given to us is this one over here.
Now we see that we have ten as the root node and we have six over here towards its left which is less
than ten.
So that's correct.
And we have 30 towards its right which is greater than ten.
So that's also correct.
And we have one over here which is less than six.
So that's correct.
And we have 20 over here which is greater than six.
But this will not be correct because whatever comes to the left of this node has to be less than ten.
Right.
So because 20 is not less than ten that's why we have to return false in this case.
So it's not enough just to check whether the left or over here.
Right.
For this particular node the left and right is correct.
But you cannot have 20 at all on the left of ten.
So that's why this in this case we would have to return false.
Now in a similar case, if this is the binary tree which is given to us, we would have to return false
because over here we cannot have any value which is less than ten.
Right.
So any value towards the right of this node has to be greater than ten.
So again because of this node we will have to return false.
Now if we are given a binary tree with only one node which is the root itself, then we would have to
return true because that's a valid binary search tree.
And then if the root itself is null, we will have to return true, because this is also considered
a valid binary search tree.
Again, you can confirm this with the interviewer when you come up with test cases.
So we have understood the question.
Now in the next video let's go ahead and think how we can solve this question.