Hello all and welcome back.
So in this video let us now move forward and discuss about the time complexity of the Czech BST approach
function, which we wrote.
So pretty sure that you must have tried the same.
Now if I talk about the complexity, let us first see that what are all the operations which we are
doing?
Okay, so in my Czech BST function, let me just close this as well.
Yeah.
In my check BST function I am finding first the left max.
Okay, then I am finding the right minimum.
So I am in a way calling on the left and the right subtree to get me the minimum and the maximum.
So some k and n work I am doing okay, then I am doing left st and right bst.
So let us try to write this down.
Everyone.
Let us say if our tree is something like this.
So the way we think in recursion, if you see something like this, what effectively are we doing?
We are saying that t of n is going to be k n.
That is to find the minimum and the maximum, right?
So I am going to each and every node to find that minimum and maximum plus I am calling.
N by two right.
So this is what I am doing after I have found the maximum and minimum, I am calling the same problem
on the left and the right subtree right.
Again, we have seen this a lot of times the complexity comes here something of the order n log n.
Right.
What if I try something like this.
Let's say it's a skewed tree.
So now we know the name of this particular tree right?
Let's say it's a skewed tree.
In that case, we saw that how t of n will be equal to.
We are again doing some work to get the minimum and the maximum, but we will be making the call to
a smaller t n minus one or n minus one.
Right.
In this case we saw that how complexity is n square.
That means in the worst case my tree or sorry, this function is having a n square complexity, which
we all know that it's little bad, right?
Now let's see why is that happening.
Okay.
And it is exactly same as the way it was in diameter okay.
So if you remember in diameter finding the diameter of my tree, same kind of thing or analysis we did.
The problem is happening.
So let's assume that this again is a tree.
So let's say this is a binary search tree.
Okay.
In this, what exactly is happening is that I am first asking this particular node to get me the maximum.
Right?
That is what I make the call left.
Max.
And this I am asking for the minimum.
Now this proper node.
What it does this left node, it will be going to each and every of these nodes.
And it can be at any depth to find out your maximum okay.
And then returns the same.
Similarly this goes to all these nodes to find out the minimum and returns the same right.
Once that is done, then I ask it again that hey, get me if you are a BST or not and the right side
again, I make this call if you are a BST or not.
Now if you see what effectively we are doing this node, the node which is on the left right, this
particular node, what it will have to do again, it will go and find out that what is the maximum here.
Okay.
This will also again go and find out that what is the minimum in some part right.
For a tree, which is a lot having a very high height, okay.
Which is a lot more complex.
This overall operations will be repeated a lots of time.
Same analysis we have done in the diameter code right where we saw that how we are asking for similar
things okay.
And if my node would have an idea like if this node would have an idea that I will be asking for the
BST and the Max.
Okay.
And is BST, this node will also be requiring, because it need to make sure that it should be smaller
than the max on its left.
It could have saved the same thing, right?
It could have used that approach or that particularly to get you the answer.
So the understanding is the same.
What I'm going to do is I am going to say to my function to bring me things which are required, right?
So let's say this is the left subtree and this is the right subtree.
Now what effectively I want is that my function returns me the max here.
And if it's a BST.
And min here.
And if it's a BST right.
That is what I effectively want.
But we know that it is not possible because see if the if we have written a recursive code, if you
are calling the same function, then it is either going to give you the maximum or the minimum okay.
So I will repeat what I am saying.
All I am saying is that you cannot say that.
Hey, I want Max from this side and min from this side.
That is not possible.
That is not a logic which you can write.
Your function is going to return you things and it can either be max or min, right?
So in this case, what we will have to do.
We will have to ask for three things min, max, and sbsd.
Okay.
Once I have these three things, then what can I do?
I can just use all of them.
Okay, so from this particular tree, I'm going to take this.
Max.
From this I'm going to take the minimum okay.
And the conditions which I have to check are again going to be the same.
So root dot data should be greater than max of left okay.
Max left root dot data should be greater than minimum of left of right.
And along with that is best left.
Okay.
And is best right.
All these things should be true, right?
And along with that, I have to also make sure that I return.
Okay.
So what I have to return.
This is going to be my answer, which I'm going to return.
Along with this, I have to make sure that I return the right value for maximum and minimum.
So how will I make sure of that?
I will return, let's say first you are returning this answer if it is best or not.
Along with that, I will return the minimum.
Okay, so what is the overall minimum of this.
It's going to be left minimum and node data right or the root data.
And I have to let's say return the maximum.
So the maximum is going to be right Max okay.
So Max let me write it right Max only.
Right.
Max.
And the root data.
Okay everyone.
So I hope this is clear as well that what are the values which we have to return?
Now we have to make sure that we are returning the right things.
If it's a BST, then I'm saying either the node will be the minimum or it will be on the left or towards
the right.
We have to just check for that value.
If we are returning these things, then we can be sure that each and every condition is checked.
Okay.
And the same complexity which was coming out to be o n square.
In worst case, we will just reduce to o n because we will now just be calling and doing some work on
each node once.
Okay, so now what I want you to do is that I want you to write this particular function, and I will
provide you with the solution.
So def check BST better.
Okay.
So in this code overall you are going to complete this function.
One more thing which I forgot to discuss.
If the root is none then you can return true.
Okay, for minimum, you will return infinity and for maximum you will return a negative infinity,
right?
So that's the base case which I've also helped you now.
So you have to make sure that you code this function and then understand how the complexity is coming
on from on square.
Okay everyone.
So I hope this is clear.
It is exactly same the way we did for diameter.
Just that I want you are comfortable in handling these cases and making your code a lot optimized okay.
Because the same is going to help you tomorrow a lot in any interview, in any contest or anything.
If you are comfortable with this approach of optimizing the code, it's a lot helpful in writing an
overall better code.
Okay, so cool everyone do give it a try.
I will be attaching the solution as well, which you can refer, but I will overall assume that you
should be able to do it properly because we have done a similar kind of problem before as well.
Okay, so do try it and make sure that you are able to do that as well.
No matter how much time it takes.
Okay.
So let's meet in the next video.
Thank you.