Hi, everyone.
So today we are going to solve this question, check if a binary tree.
Is a birthday or not?
OK, so first of all, what is so BSU stands for by history?
OK, and what is the property of a beast so invested?
The properties of Vesti are very simple.
So suppose you have this root node.
OK, so if will go left, then all the nodes in the left hand side, so their data will be less than
the data of the root node.
Similarly, if you will go in the right hand side of the root node, then.
The data of all the nodes.
Will be greater than the data through a..
OK, so this is very simple property of obesity.
OK.
And so what is the input?
So the input given is basically a binary tree and we have to return a boolean value.
OK, whether that by the tree, if the banditry is about, I will return.
True, if the binary trees not vestey then I will return false.
OK, so how can I solve this question.
So there are two ways to solve this question.
OK, so the first we.
So the first race, basically, we know that in order traversal of a BSD sorted, OK, this is the property
for Besty, the in order traversal of best is sorted.
So very simple.
OK, so consider this example.
This is a binary tree.
So what is in order traversal?
So in order to resources, first you visit the left subtree, then the current node data and then the
right subtree.
OK, so Ali, are now let us consider this binary tree and now let us perform it's traversal.
So what will be the traversal.
So suppose this is the.
So this is the root node.
So terror cell will be one, then two, then three, then four and then five.
OK, now you can check this is basically sorted.
One, two, three, four, five.
This is sorted so I can see that this binary tree is basically Vesti.
OK, so this binary tree is besty because it's traversal is sorted and only BSD there was in reversal
sorted.
Now let us perform the reversal of this bindery.
OK, so it will be one, then five, then three, then four and then six.
OK, so basically this is not sorted since this is not sorted.
So this by military is not besty.
OK, so this is not Vesty.
You can see season or number four.
OK, so this normal four qualifies for bisdee, but this note number five does not qualify because in
the left hand side you have one perfectly fine.
But in the right hand side you have this node four and four is basically less than five.
So this binary is not Vesti.
OK, so the first way to solve this question, what we will do, so we will perform the travesty of
the best and let's say we will store the result in energy.
OK, so what we will do, we will restore the traversal of the given by Nutri in an area.
So this area will contain the reversal of the binary tree of the given by Nutri.
Then I will check whether this area is sorted area or not.
If this is sorted, then I will return to the given by is best.
If this area is not sorted, then I will return false.
So this binary is not the best if that is not sorted.
OK, so very simple approach.
So what would be the time and the space complexity of this approach?
So time complexity is basically so we have to go through each and every node.
So suppose there are end nodes so time complexity will be big off and and what is the space complexity.
So it will be big off and OK, we have to store and node.
So what is and is basically the total number of nodes present in the binary tree?
OK, so this is the time in this space complexity of using this approach.
Now, one thing that I want to share is basically so what we can do here is so there's no need to create
this.
OK, there is no need to create this idea.
So what we will do so we will take two pointer, previous pointer and the current pointer.
And while we are doing the traversal.
While we are performing the traversal we will check, previous data should be less than the data current
data.
OK, so if this condition is always valid, then basically the error is sorted, then sorted so you
can return bisdee the given by degrees.
And if at any point this condition fails, basically previous data is greater than current data, then
you can return that.
The given by Nutri is not about because it's in at least not sorted.
OK, so here, how do we check whether it is sorted or not?
Basically we take two pointers, so previous and current pointer and we will check that previous data
should be less than the date of the current pointer.
OK, so this weekend can.
So instead of creating this area when we are performing the traversal, we can check this condition
for every node.
OK, so in this way the time complexity is still big often, but the space complexity will be Goffman
because there is no need to create.
This Eddie.
OK, there's no need to create this, Eddie.
Now, let's discuss the second way of solving this question, OK?
So let us take this example, four to five, one three, so I have this for two, then five and I have
one and then I have three.
OK, so let's discuss the second way of solving this question.
So what we're going to do here is so basically each node has some constraint.
OK, so each node has some constraint and what is that constraint?
So let's discuss that constraint for the root node.
So this value, this value can be from minus infinity to plus infinity.
It can be anything, OK?
Root data can be anything but if it will go in the left hand side.
Suppose the input is basically about, OK, so suppose I am discussing the property of about OK, I
am discussing the property, everybody.
So if it will go in the left hand side.
What can be the data of this value, what can be the data for this?
Not so.
The minimum value can be minus infinity, but the maximum value can be four by four, because four is
the root node.
OK, so the value of this node will lie between minus infinity to four, because this is the property
of the best that if it will go in the left hand side.
So the left the debate of the left node will always be smaller than the route node data.
OK, so for this node, this is the constraint.
The value will lie between minus infinity for OK.
Now suppose you again go left.
So for Naude, No.
One.
So basically for disaccord, the minimum value will be minus infinity, but the maximum value can be
two only.
OK, the maximum value will be two if you will go in the right hand side.
So the minimum value will be to and the maximum value will be for.
OK, so this for the maximum value will be for.
So the only possible in this three.
Now, if you were going the right hand side.
So basically, it's minimum wage level before and it's maximum value will be infinity.
OK, so.
Each node has constrained OK, each node data, each node data is bounded by a constraint that its maximum
value will be, it will lie between the minimum and the maximum value.
Each data will lie between a certain minimum and the maximum value.
OK, let us take one more example.
So suppose I have five then let's say I have this X and here I have Y.
OK, so here I have Z and let's say here I have and here I have B.
OK, so.
This value can be from minus invader infinity.
OK, so its value, so the value will be minus infinity and the maximum value will be five.
If you will go again in the left hand side, the minimum values still minus infinity, but the maximum
value is X.
OK, now for Y.
So what can be the values of.
So basically the minimum value will be five and the maximum value will be infinity.
For this note, the minimum, if you are going in the left hand side, so basically the minimum value
will be five.
OK, so this five, the minimum value will be five and the maximum value will be by OK, if you are
going in the right hand side.
So the minimum value will be way and the maximum value will be infinity.
OK, so what is the second approach.
So second approach says.
Basically, you check the constraint of every node.
OK, I will check the constraint for every node if the constraint is valid, if all the nodes.
Are having this constraint then it is about race.
It is not about.
OK, I'm repeating myself, the second approach will go to each and every node, OK, approaches, go
to each node and check their constraint.
OK, what is the constraint?
So this is the constraint of data constraint.
If every node follows the data constraint, OK, it is very simple.
If every node follows its data constraint, then it is a BSD.
Otherwise it is not OK if every in order for the constraint.
So if it is true then the given binit it is best raise.
The given by Nutri is not ok.
So I think this approach, number one, is very easy to implement.
OK, so what we are doing, we will just perform the traversal and we will take two point up us point
and point out.
And we will we will have to check this condition.
OK, then we can return whether the.
Guarantees BSG or not, but the second approach, I think, is a little bit difficult.
So let us implement the second approach.
OK, so what we will do is first let us take this example.
Also five 146.
OK, now let us check whether this five 146.
So I have five one four and then I have three and six.
OK, so its value can be from minus infinity to infinity and its value is five.
So this note is correct.
If I'm going on the left hand side, so its value will be from minus infinity to five and one lies between
this.
OK, so this node is also correct.
Now check this node for.
So it's minimum value is basically five and it's maximum value is basically infinity, and four does
not lie between five and infinity.
OK, so that means this tree is not a beast.
OK, this tree is not beast because fall does not lie between five and infinity.
OK, so what will be our approach?
So we will take the help of regulation, we are implementing second approach.
OK, so we will take the help of regulation.
So this is the left subtree.
This is the right subtree.
OK, so what we will do, so I will call the functionality of the neural function is is bisdee.
So I will call the function on the left hand side, the left hand side should be left subtree should
be bisdee.
Right.
Somebody should be best and for.
I will check whether the days lag between minus infinity to infinity.
Very simple.
OK, so your condition if the left to is a body, if the right is a beast, and if the narrator lies
between minus infinity to infinity, then I will return to that the given prize bastia that I will return
false.
OK, so I hope you understand the logic.
Now let us write the code, ok.
So basically, this is a legitimate question validated by necessity.
OK, so now let us write the code.
OK, so one thing.
So I told you that the value of fruit will basically lie between minus infinity and basically plus infinity.
So let us define what R minus and plus infinity.
OK, what what is the meaning of minus infinity and what is the meaning of plus infinity.
OK, so basically in C++ integer itself, 32 bits.
OK, so that means the maximum value of integer can be to the power 31 and the minimum value of integer
can be minus two to the power to be one minus one.
OK, so this is basically let's call it it is nearly equal to the power nine.
And similarly this is also nearly equal to minus 10 to the power nine.
OK, so by plus infinity.
OK, so this plus infinity.
So it should be good.
Then at about nine let's call it ten to the power 10 and similarly this minus infinity.
So this should be listin ten to the power minus the power line.
So let's call it minus 20 the power then.
OK, so these are distributed.
So they are inclusive.
OK, so for root, root can take the valley of basically minus 10 to the power line and it can take
the valley of the power line.
OK, so now let's ride the gold.
So this is basically a little problem.
OK, so their function is bull and then it's basically a root.
OK, so let us create a helper function so that the helper function will be able.
So what this function will take?
This function will take.
Root node.
And the minimum and the maximum value of the loot.
OK, so here the what is the minimum?
The maximum.
So the normal life between minus infinity to plus infinity and both are inclusive.
OK, so minus infinity is basically minus 10 to the power nine and plus introduced into the lower nine.
OK, so what I will pass.
So I am passing.
These are inclusive.
So that means if I want to exclude this I can write minus 10 to the power, Ten Commandments, the power
then.
But this number is big so it cannot be stored in integer.
So I will store it long.
Long.
OK, this number is big, so I cannot turn it in, so who have to store this number in a long, long
and similarly for this?
OK, so I have to take long, long.
So this route will lie between two variables, minimum and the maximum, so the minimum value is basically
you can pass the default argument, so then minimum will be minus 10 to the power 10.
OK, so 10 zeroes, one, two, three, four, five, six, seven, eight, nine, 10.
OK.
And similarly.
The maximum value of fruit can be what is the maximum value of fruit, so it can be 10 to the Barberton.
OK, it will be tendered about so one, two, three, four, five, six, seven, eight, nine, 10.
And the rules, basically.
So one thing.
So here I am digging.
Down to the bottom, you can also take 10 to the power, 11 or 10 to the power to end and so on, but
the power then is will do our work.
OK, so this is more than enough.
It will do our job.
And similarly, ministered to the power then will do our work.
OK, so now what we have to do.
So let us ride the bike.
So what is the best case.
So if through dismal IFPRI does not exist, then I can say that given by Nutri is basically biased.
So I will return to OK now if we have to do first, let us check whether the left is biased or not.
So let us call the helper function so I will pass the left subtree.
So rude and left.
Now, what is the minimum value, what is the minimum value for the left subtree, so it will be same
as minimum value for the root.
And what is the maximum value?
So basically, the maximum value will be route data.
OK, so Rotaru value.
OK, so one thing.
So if you have a binary tree.
This is one, and this is one, so basically this Binit is not bisdee, OK, this is not Vesti because
its range is between minus and to infinity, but its range is between minus infinity to one.
OK, so basically this one is this one, OK?
And this one is basically.
So this is this type of this type of record means this one is not included.
OK, this is not included.
So this is excluded.
So since this one equals close to this one, so that means this is not about OK, this is not about
because strictly left values should be less than root values.
OK, this is not less than articles two.
This is strictly Leston, OK?
So that's why if the input is this now put this this is not about OK.
And similarly, let us check whether the right surprise you or not.
So let us call the helper function.
I will bust the right subtree.
Now, what is the minimum wage, so minimum values?
Nothing.
It is.
Rude value.
OK.
And what is the maximum value, so the maximum value is plus infinity, basically this number 10 to
the power.
OK.
Now, our trees vista if and only if left some trees.
So if left and right surprised Besty and the value of fruit.
And the root value.
Basically, it lies between plus infinity and minus infinity.
OK, so this condition.
So the value of fruit.
So it should be basically greater than the minimum value.
And it should be.
Less than the maximum value, if these four conditions are true, then I will return to.
In the elford, I will return false.
OK, so let's call the helper function from Dimin, so return helper, when I will pass, I will pass
on the road.
OK, so these are default arguments.
So let us not our call, and then we will try to submit our code, OK?
OK, so now let's meet our good.
OK, so our court is working fine.
OK, now let's see what we are doing here.
OK, so this helper function is doing all the work.
OK, so this is taking root.
So this is taking the minimum value of the root, which is which I'm calling minus infinity.
And it is calling the plus it is calling the maximal of the root, which which I'm calling is plus infinity.
OK, so four root node.
The value is between minus infinity open bracket and plus infinity open bracket.
OK, so the value of fruit can be close to two to the power to divine, which is the maximum value for
an integer.
OK, so and this value is equal to around 10 to the power nine.
So to the power nine is basically included in this.
OK, so that is about nine will be included from minus 10 to the power 10 to 10 to the power then.
OK, so no problem then.
If the root is nil, obviously we can directly return.
True, because the given binary will be bisdee.
Now I'm calling on the left subtree, then I am calling on the right subtree and then I am checking
the condition.
So if the left is the right, surprise Vesti.
And now here I am checking the constraint on the root node.
OK, so if the value of root node is greater than the minimum value and the value of node is less than
the maximum value, then return to azn false.
OK, so very simple.
What is the time complexity of this approach?
So basically we are going through each and every node.
So if data and NATO time complexity is big off and now what does this space complexity.
So the space complexity you can say or Draffin if you are considering the cost.
So basically we are using recursion.
So the recursion we have a call stack.
So if you will consider this memory, if you will consider the constant memory, then it is ultrafine.
Otherwise it is order of one.
OK.
Now, if you didn't like this approach, we also discussed about the first approach, what we can do.
We will simply do traversal need traversal and we will store the sell output in an eddy.
And if this stays sorted, then the then basically the binary trees, BSG either remains or does not.
OK, so this is very simple to implement.
It is very easy to implement.
It can implement it yourself.
OK, so in this case, also the time complexity we have already discussed Magoffin and the space complexity
is also big.
Often if you are creating the very.
But if you will write code in a good matter, then there is no need to create this area.
You can take two pointer, three pointer and current pointer and you can easily compare the date of
these two points and you will be able to solve this problem in open space using the Internet.
OK.
So if you have any doubt in this question, you can ask me.
OK, thank you.