Welcome back.
Let's now go ahead and write the function to check whether the binary tree which is given to us is a
valid binary search tree or not.
So over here we have the class node.
And then we have the binary tree class over here.
And then we have the insert function, which we have discussed in a previous video.
And using this instance method I have created a binary tree over here and these values have been inserted.
So we will now go ahead and write the function to check whether this binary tree is a valid binary search
tree or not.
So let's go ahead and write the function.
So let's have a comment over here.
So this is going to be the function to check.
Whether the tree is a valid binary search tree.
So let's call this function.
Check if.
Valid.
BSD.
Now this function is going to take in the root of the binary tree.
So it's going to take in the root.
And then now we're going to implement this as a recursive function as a recursive solution.
So over here we're just going to return what we get back from a helper function which will check whether
that the binary search tree with that particular node where we are currently at is a binary search tree
or not.
So let's now see how we implement this.
And it will become more clear.
Now this helper function is going to take in the node.
So that's the root over here.
And then the initial bounds are minus infinity.
And infinity.
So these are the bounds initially.
So we have seen that at the root we can have any value.
And still the binary search tree is going to be valid.
Now let's go ahead and write the helper function.
So we have const helper.
And this function is going to take in the node and the minimum value and the maximum value.
All right.
Now, once inside the helper function, first we will just check if the node is equal to null.
So if the node is equal to null.
Then we will just return.
True.
All right.
So we know that because we've seen also in the previous video in the test case.
Also, if the binary search tree is just a null tree, we will just return true.
And even in recursive calls, when we reach a level where the left or the right is just null, we will
just return true.
So that's why this is our base case.
So let's just write a comment over here.
So this is the base case.
Now let's proceed.
If this is not the case, then we are going to take the value of the node.
So let's say let value is equal to node dot value.
And then we're going to check whether the value is between the bounds.
So we have the min and max bound over here.
Now if it is not within the bounds then we know that it's not a valid binary search tree and we can
just return false.
So let's check that.
So if.
Value is less than equal to the minimum value or if value.
Is greater than or equal to the maximum value.
So if either of these is true, then we know that the value is not in between min and max, right.
Because we know that ideally the required condition is that min should be less than value and that should
be less than max.
So this is what we want.
Now if any of these two is true then this is violated right.
So then this is violated.
And in that case we know that we don't have a valid binary search tree and we can just return false.
Now if this is not the case then we proceed further.
Now we are going to check whether it's the nodes.
So we are at a particular node.
So we're going to check whether the node's left subtree and right subtree.
Is a valid BST.
So that's what you're checking now.
All right.
So let's go ahead now for checking whether the left subtree is a valid subtree.
Valid binary search tree.
So let's have const is left BST.
So let's have a variable is left BST.
And this is going to call the same function the helper function recursively.
So only we are going to pass the node dot left over here.
So helper and the node is going to be node dot left which you are passing to the helper function.
And then we have seen that when we go left we are going to change the maximum right.
So when we go left we are changing the maximum.
And when we go right we are changing the minimum.
So that's what we have discussed in the previous video.
So over here we are going left because we are passing node dot left.
So when we go left we are changing the maximum.
So we are not changing the minimum, but the maximum is going to be changed to the value.
Now why is it that we are changing the maximum?
Because we know that when we go left, we need something which is less than the value which is there
at the node.
Right?
So that's why the maximum possible is something that is less than the current value.
All right.
So that's why we are changing the maximum to value.
Now let's go ahead and also check whether the right subtree is a valid BST.
So for this let's again have const is right.
BSD.
So that's a variable.
Now this is either going to be true or false.
And then we're going to call the helper function recursively and pass node dot right.
And because we are going right we are going to change the minimum to value.
And the maximum is staying as it is.
Now each of these is going to be true or false.
So when it returns and then we are just going to return true if both of them are true.
So we are going to say return is left BST and and is right BST.
So if both of them are true then we will return true.
Otherwise we will return false.
So this is how we have solved this question.
You can see that because this is a recursive implementation, the number of lines of code that we have
to write is very much less.
Now let's go ahead and try to see whether this binary search tree is a valid binary search tree or not.
This binary tree over here.
Now, before we run the code, let me just draw this over here so that we can visualize it.
All right.
So I have just drawn the binary tree over here, which we have created using the dot insert instance
method.
So we have ten over here.
Then we have five and 20.
So that's five and 20 over here.
Then we have three and seven.
So three and seven is over here.
Then we have 15 and 30.
So 15 and 30 is over here.
And it goes on like that.
So we have null and four.
So that's why this over here is null.
And then we have four then null and null.
So that's the left and right of this node over here which is seven.
And then we have null and 17.
So we have null over here this is null.
And then this is 17.
And then we have null and null.
So that's the left and right for 30.
And then we have null and null which is the left and right for four.
And then we have null and 18.
So that's this.
So the left of 17 is null and the right is 18.
So this is the binary tree which we have created.
Now let's call the function which we have just now returned to check whether this binary tree over here
is a valid binary search tree or not.
Now before we run the code, what's our expectation?
We can see that this is actually a binary search tree.
Right?
So everything to the left of ten is less than ten.
Everything to the right of ten is greater than ten.
And it's true for each of these nodes.
Right.
For for example, for five everything to its left is less than five, and to its right we have greater
than five.
And for 20, everything to the left of 20 is less than 20, and everything to the right of 20 is greater
than 20.
So this is actually a binary search tree.
Binary, uh, valid binary search tree.
Now let's go ahead and run the function.
So let's call check if valid BST.
So we're going to call the function.
And we are going to pass in the root of this binary tree.
So tree dot root is what we pass in as a parameter.
And let's now go ahead and run the function and see what we are getting.
Okay.
We have an error.
So let's just check that over here.
Node is equal to.
We are checking it right?
We are not assigning it to be null.
So that's an error.
All right.
So let's run it again.
And yes it's working.
So you can see we are getting true.
That is we have checked that this binary tree over here is actually a valid binary search tree.
Now let's just walk through the code and see what's happening over here.
So again this is the binary tree.
And then we are calling the function.
So we are over here.
Now we are calling the helper function.
And we are passing the root node which is ten.
So let's just take a pen and.
See what's happening.
So we are passing this node over here and then minus infinity and plus infinity.
Now we are coming inside the helper function.
We see that the node is not equal to null.
So we come over here and we take the value which is ten.
And we are checking is the value within the bounds minimum and maximum.
At this point it's just minus infinity and plus infinity.
So we don't get any of these.
These none of these two conditions is true.
Right.
So we come over here.
So we are done with this.
So this is validated.
Now we go ahead and over here we are going to check whether the left binary trees that is this part
over here we are going to check whether this is a valid binary search tree or not.
So let's go ahead.
So we are over here.
Now let's continue.
Let's just change the color of the pen.
Now we are past.
We are again calling the helper function.
We are passing node dot left which is this node over here.
All right.
And we are changing the maximum value.
So min is still negative infinity.
So min is negative infinity.
And max is going to be the value which is ten.
So max is going to be ten.
All right.
So we are inside the helper function.
And we are checking is the node equal to null.
No it's not equal to null.
So we come over here we take the value which is five.
And then we are checking is five.
Within the bounds we know that minimum is negative infinity.
So that's fine.
So that's not going to be a problem because the value is anyway going to be greater than negative infinity.
But then the maximum has to be equal to ten.
So max is ten.
So let's check.
We are checking that over here is the value greater than equal to ten.
No that's not the case right.
Five is not greater than equal to ten.
So we don't go inside over here.
And then we come over here.
So this has been validated.
Now we are going to check is the left subtree of this particular node a valid binary search tree.
So we are going to check this over here.
All right.
So this is what we are checking.
And let me change the color of the pen.
So we are coming over here and we are passing node dot left which is this node over here.
So this is passed.
And at this point we are going to change the maximum value to the value which is five.
So value is five.
So max is going to be five and min is still negative infinity.
And again we are inside the helper function.
Now over here node is not equal to null.
So we still don't return true.
And then we take this value which is three.
And over here we are checking whether is three greater than equal to five.
That's not true.
And then value is it less than equal to negative infinity.
That in anyway will not be true.
Right.
So we don't go inside over here and we come over here and we are going to check whether its left subtree
is a valid binary search tree, at which point we are passing node dot left which is null.
So when we come again inside the helper function, it will return true.
So we have seen that its left subtree is a valid binary search tree.
So now we are going to its right subtree right.
So we come over here and we are passing this node which is four.
So we are passing this four over here.
And at this point we are going to change minimum to value.
Value is equal to three and maximum is not changing.
So maximum was already five right.
So minimum is going to be three.
And maximum is going to be five.
So minimum is three and maximum is five.
Again we come inside the helper function.
We see that this node is not null.
And we check is four within the bounds.
So minimum is three and maximum is five.
And the value over here is four.
So it's actually within the bounds.
So none of these two conditions is true.
So we don't return false.
So we come over here and we are checking whether its left subtree is a valid binary search tree.
So we are passing node dot left which will be null.
So again when we come over here we will just return true.
And similarly when we come over here we will see that the right subtree is also a valid binary search
tree.
Because node dot right is just going to be null.
All right.
So again we come back.
So we have seen that for node three its left and right subtree are valid binary search trees.
So this over here this is going to return true.
So this is going to return true.
Now we go ahead and check this one over here.
So we come over here and we will check whether this is actually a valid binary search tree which is
the right subtree of node five.
So let's just clear this space over here.
So we are.
We are coming over here now.
So let me just make some make this clean so that we can keep track of this.
So at this point.
We come over here.
So this this call will be part of is right BST where the current node is five.
Right.
So we are going to pass node dot right, which is this node over here.
And then the value value is going to be five over here which is the min value.
And the max value already was ten right at this point.
So max is going to be ten.
So we are going to check whether this node over here is in between 5 and 10.
So that's going to be checked over here right when we again come inside the helper function with min
as five and max is ten.
So we see that the node is not null.
So we take the value which is seven.
And we are going to check is seven less than equal to five.
No that's not true.
And is seven greater than equal to ten.
No that's not true.
So we don't go we don't return false.
So we come over here and we check for its left and right subtree because it's null.
It will just return true.
And in this way we have seen this also is going to return true.
So for this particular node its left subtree is a binary search tree.
So it returned true.
And its right subtree is also a valid binary search tree.
So this is also returning true.
Right.
So for this particular node right.
So where the value was five this is going to be true.
And this is going to be true.
Therefore we will return true and true.
So that means this is going to be true because both of these are true from this part we are going to
return back true.
So we have seen that when this was the node, its left subtree is actually a valid binary search tree.
All right.
So let me just make some space over here and clean this up a little bit so we can keep continuing to
trace the code.
So we have seen that this this was part of the call for the left binary search tree.
This call over here right where the node was ten.
Now this has returned.
True.
Now we proceed and we are going to check whether the right subtree which is this over here we are going
to check whether this is actually a valid binary search tree or not.
So that is part of this call over here.
Now we are passing node dot right which is this node over here.
And value is going to be ten.
And maximum is just what was previously maximum which was infinity.
So we come again inside the helper function min is going to be equal to ten and max is going to be infinity.
So again we come over here the node is not null.
So we are taking the value which is 20.
Then we are checking is 20 less than equal to min which is ten.
No that's not true.
And is 20 greater than equal to infinity.
That's not true.
So we don't go inside over here.
And then we come over here and we are proceeding.
And we are going to check is the left subtree of this particular node a valid binary search tree or
not.
Which is this part over here.
All right.
So we are passing this node over here.
And again we continue.
Right.
So over here min is going to be what was already min which is ten.
And max is going to be the value which is 20.
So we have ten and 20 as the value over here.
And again we come inside the helper function.
We see that this actually is valid.
So it does not go, it does not continue and return false.
So then we proceed and check is the left subtree of this one a valid binary search tree.
And because it's just null it will come over here in that particular call and return true.
So the left is a valid binary search tree.
And we proceed and check for the right.
Right which is over here for this call.
Again we do the same thing.
This is going to be the value.
And then we check whether this is in between the uh the the value and max in that case.
Right.
So Max is is going to be at that point.
20 and min is going to be 15.
So 17 is in between these two values.
So again, yes it's true.
And we continue in this part to check whether its left subtree is a valid binary search tree.
And because it's null it will just return true and its right subtree.
Also we find is a valid binary search tree because we have 18 and 18 is greater than 17 and less than
20, which are its bounds.
So in this way this is going to return true.
Right.
So again its left also for node 15 return true because it was null.
So we see that the left subtree over here is going to be true because this will return back true.
This will return true.
And then we will check for its right subtree and we will pass 30.
And then the bounds are going to be that it should be less than infinity but greater than 20.
And we see that its true.
Again it will check over here whether its violated.
It's not violated.
So we are going to check for its left and right subtree which will return true because it's just null.
And then we will just return that this is true.
So this also will return back true.
So for this node we get back from the left and right true.
So this is also going to return back true.
And then when the when we called the is right BST function right.
So this one over here when we call the helper function passing this node over here this is going to
return true.
So for the node ten is left BST is true and is right BST is also equal to two is also equal to true.
And because both of these are equal to true.
So we are just going to return true when from for over here.
Right.
For this call for the first call this is going to return.
True because we have seen this and this is going to be giving back.
True.
So in this way we have identified that the given binary tree which is given to us is actually a valid
binary search tree.
Now let me just clear this up and let's take a quick look at the space and time complexity of this solution.
Now what's going to be the time complexity.
The time complexity is going to be O of N, because you can see we have to traverse through every node
over here and check whether it's within the bounds.
And then we proceed and check for its left and right subtree.
So the time complexity is going to be O of n because we have to traverse every node.
And the space complexity is going to be O of height or the maximum depth of this tree, because this
is going to be a recursive solution.
And we're going to take up space on the call stack.
And in the worst case.
The space complexity is going to be O of N, because if the binary tree was something like this, right
where we just have nodes in one direction.
So this looks like a linked list.
So in this case we would have to go all the way down.
Right.
So in that case the call stack is going to take space of the order of n.
So that's why in the worst case the space complexity is going to be O of n.