Hi, everyone.
So in the last video, we discussed this question, find the diameter of a binary.
So in this video, we want to discuss a better approach, better approach in terms of time, complexity.
So this is how we will utilize our resources.
This is the left subtree and this is the right Sabry.
So what will do so rude will ask the left, hey, find out the height and the diameter.
Solarcentury will determine its height and it will dondi diameter.
Now Ruth will call on the right subtree.
Hey, right.
Find out your height and diameter.
So I have probably done the height and the diameter so we know what is left, right and left diameter.
We know what is right height and right diameter.
So can we find out overall height and overall diameter?
So what will be the overall height?
So overall height will be one plus maximum of left and right.
Right.
So this will be one plus maximum of left and right.
Right.
And can we find out what is the overall diameter?
So overall diameter will be.
So I have three options.
So I take maximum of what is the first option left out plus right.
So first option is left out.
Plus right eight.
Second option is left diameter.
Third option is Radiometer.
So we can find out the overnight and we can find out the overall diameter, so root will return overnight
and overall diameter simple.
So that is our approach.
So first, let's discuss the base case.
So case will be traditional, so if Rudisill is the first step.
So if traditional, but without zero vertical diameter to zero, now the second step is basically hypothesis
step or the induction step.
So in this step, we will be able to find out the left, right, left, diameter, right out and right
diameter.
And what is the third step?
So third step is basically finding out the overall height and diameter and the steps or this step is
basically the third step, finding the overall height and the overall diameter.
So what we want to do, so we want to return to things, I want to return to things so we can create
a class.
So I want to return a pair of these two things so I can go to class, Gaspare.
First will be debate in Detroit, and second thing is Daym.
So I know what the function will be up here, and let's say the name of the function is find out the
height and the diameter, it will take root as input and it will return dippie.
So it will be done up here and it has two things height and the diameter, or if you want to make the
call for the generic so I can create glass like this glassware.
So instead of this height and diameter, I will call it first and second.
I am calling it first, I am calling Dimetapp Second.
So if you want to make the class, if you want to make the class of beer generic so you can do also
like this in first and second, but there is no need to do all this thing because we have Invicta per
class.
So we have inbuilt Berglas in C++ and this class has implemented using template.
So this is the code for the Beltway class, so instead of integer first, it is the first and similarly
it is B second, and then you will create the object of this class.
You will give the value of t, you will give the value of.
So let's write the code.
So this is our previous quote, let's find out everything or let's reset our good.
So I'm resetting my code, so what I want to do.
They don't have the function will be their superiors and world class and C++, since it is implemented
using template.
So the first value height is going to be integer.
The second value diameter is also integer.
And let's say the name of the function is height diameter.
The name of the function is higher diameter.
So it will take.
Input.
And it will be done up here.
And finally, what we will do so here, we will call this function.
So let's call this function.
Hi, Daym.
We will pass it, Ruth.
So dysfunction and it does appear so let's create a period.
Fear of indigenous communities are heightened diameter, let's name it be.
And what we need to return, so we need to return integer and I want to return diameter.
So what is diameter?
Diameter is the second value.
So I am assuming they do this second.
So I will write P Dot.
Second.
So what I'm doing here, so I'm calling this function Dimitar, I'm giving your route so this function
will return me what is the height of my tree and what is the diameter of my tree?
So it is a stunning integer integer.
So this is an multiclass Glaspie integer first and indeed second.
So why integer, because you are giving Integer an advantage, because you are giving integer and what
you need to do.
So I'm assuming first is right and second is diameter, and this function returns are daym, so I am
returning Bédard second.
So I am returning the diameter value and now we need to write the code for this function.
So let's write the code.
So basically, if traditional.
So if traditional, my height will be zero, my diameter will be zero, and I need to return a pair.
So let's create a pair.
Fear of contagion combined.
Let's name it be so what out first with our first sight, Heidi?
Zero.
What is that second winner is diameter, diameter, zero, and then you can be so then we are turning
up here.
So now let's discuss about the next step.
So what we'll do, let's call let's try to find out the height and diameter of all subtree so left unsaid.
So we'll call dysfunctioning diameter.
We will pass the left necessary.
So hydrometer function will give us the left answer, what is left unsaid, left and left, right and
left DAYM and let's call the recursion.
So this is right answer.
Called the function radiometer and give it the right subtree.
So what we are doing right now, so this is Salvatore.
So I'm calling the function on the left subtree, it will return a pair of intelligent design, I'm
calling it left unsaid, so it will return a pair left unsaid.
So the first values are the second values Dimery, similarly, the first values site and the second
one is damaged.
So now we have left answer and we have a right answer.
Let's find out these four values.
So let's create variables.
Integer left eight.
This is.
Left unsaid, darte first.
So what is left diameter?
This is.
Left unsaid, dot second.
Now, what is right, right, so this is.
Right, answer that first.
And what is right, diameter, so this is.
Right answer, Nade second.
So now we have all these values, we have these two values and we have these two values, and now it's
time to find out the overall height and overall diameter and then we will return the pair.
OK, so that is the function espere.
So we construct a compared with the overall height and the overall diameter and then we will return
dispair.
So let's write the code for finding out the overall height.
So in height, this is overall height and what is our own height, so this is one plus.
Maximov left out a comma right out.
And what is so little diameter?
So.
What is the overall diameter?
So it has three options, so the maximum of what is the first option left out plus right eight second
option is.
Left VanMeter and third option is right to Dimitar.
So we know what is all right and so we know what is right and what is our diameter.
So now we need to return a here.
There didn't have the function espere.
So we will create a bear.
So bear of indigenous or to be subpoenaed first.
Is this all right?
And be second is the overall diameter.
So after constructing the pier, we need to return it also and return.
B.
So now I think this court will work.
So let's run this court and then we'll submit.
So now let's Amitava called.
OK, so basically our goal is working.
Now let's discuss the time, complexity, and then we will discuss how it will work.
So first of all, let's discuss the time, complexity.
So what we are doing here, we are calling it a collision on the left.
We are calling it a collision, the right subtree.
We are calling records for the left subtree, we are calling an occasion for the right subtree, so
basically we are going to each and every node and let's see how much amount of work we are doing for
each and so for each A. This is constant amount of work.
This is constant work, this is constant work, this is constant work.
So basically we are going to each and every node and for each and what we are doing constant work.
So the total time complexity will be N.K..
So the total time complexities we are going through each and every note and for each node, we are doing
a constant amount of work.
So engaged, basically same as big often.
So now you can see in the previous solution, our time complexity was and multiply by eight.
So now our time complexity is big off.
And so this solution is much better than the previous one.
And now let's take an example and now let's see how our solution will work.
So first of all, let's take a very simple example, so if tree has only one or so, if there is only
one node, but we will do so, we will call the function on the left.
So for the left, Sabry.
The height is zero and zero zero zero, you will call the function of the lights of the idea zero and
the diameter is zero.
Now for this node you will calculate the overall height and overall diameter.
So what is height?
Height is left height, maximum of left, right, right, eight plus one.
So height is one.
And what is diameter.
So three option.
So the first option is left out.
Right out, which is zero level diameter, which is zero, right down to zero.
So maximum of zero zero zero.
So it will be zero.
So basically for one node, if my tree has only one node, height is one and diameter zero diameter
should be zero.
Because if there's only one node, then diameter should be zero.
Right.
Because for this diameter maximum distance between two nodes, maximum distance between any two nodes,
but there is only one node, so there will be zero.
So we know if there is only one node.
The height is one and the diameter is zero, so let's see, let's take one more example.
So if this is Maitri.
If this is tree, then what should be the output so high, it should be too and diameter should be two,
OK, diameter should be two and should be two.
So let's see how it will work.
So for one node, we know height is one and diameter zero.
Similarly, if there's only one node, we know height is one and diameter is zero.
Now for this node.
What is the overall height.
So the maximum of left, right, right, right.
Which is one and one plus one is two.
So it is two.
And what is diameter.
So diameter is the maximum of left height plus right height.
So which is two.
Left diameter, which is zero right diameter, which is zero.
So we to take the maximum of these three, so the output will be two.
So diameter is two.
So, Heidi, still dealing with those two and which is the perfect answer, so you will return the time
you will get to commit to and you are returning the diameter.
So now let us take a complex example.
So let's take a victory as input and then we will see what we decide in diameter.
So if this is my three, one, two, three, four, five, six, seven.
Eight and nine.
So what will be the correct height and what is the correct diameter, so height is basically one, two,
three and four, so I should be fought for this tree and diameter is so one, two, three, four and
five.
So diameter should be five and it should be four.
So when will on give me the height and diameter to call on for medium height and diameter and for one
node for when or what will happen.
You will go on the left, you will get zero zero.
You will call right.
You will get zero zero.
And for one node, if there is only one node we know the answer will be one zero.
Similarly, if there is only one note, we have seen that the height is one diameter of zero.
Height is one dimwitted zero.
Height is one diameter of zero.
Similarly for this, Naude height is one diameter zero Lalaji.
So if one or two, what is the height?
What is the overall height?
So height is basically a maximum of left and right, which is one plus one.
So height is two and what is diameter.
So diameter is basically left height plus one plus one is two level diameter is zero.
Right diameter is zero zero zero and the maximum so two.
So it will return to Clamato.
Height is two, diameter is two for this node.
So this is the same situation.
So it will also return exactly the same thing, Heidi, is to Demetris to.
So now let's see for node three to four, Naughtie, what is the height?
So basically, it is Maximov, left, right, right, right, plus one, so for three, it will be three.
And what is the diameter, so diameter 40 is basically left out, plus right out, two plus one is three,
left diameter is two.
Right, diameter is zero.
That makes some of these two is three so high, it is also three and diameter is also three.
So now let's find out the answer for one, two for one.
What is the height?
So height is maximum of left height and right eight plus one.
So it will be three plus one four.
And what is your diameter?
So diameter four one is basically the left height plus right eight.
So two plus three comma left diameter which is two right diameter which is three.
So the maximum will be five.
OK, so this value is five.
So we need to take the maximum.
So maximum is five.
So diameter is five.
OK, so what happened?
OK, so this is Natalie, so now you can see.
So now you can see the height is four and five, and which is the right answer, height is for and diameter
is five, so you will get a pair here and you are returning the second value.
So second value was diameter.
So that's how everything was working.
And the time, complexity of this code is basically big often.
So this approach of returning to things from what we are doing so annoyed is calling on another note
and that note is returning to things at once, this calculating both the things at once in only one
location call, and it is returning to values, or you can say it is returning multiple values.
So this technique, this approach is used in many problems.
So, for example, if there is a problem in which you find out four things.
If you were to find out four things at once, then you can use this approach.
So what we will do so this class is only for two things.
In this case, if you want four things at once, so you will create a glass, your own glass, let's
say glass information.
You want four things at once and you will write these four things first thing second, third and fourth,
and then identify what the functional information so you will return an object of glass information.
So this approach, this technique is very useful going forward.
You may encounter such problems in that problems.
In order to get a good time complexity, you need to return multiple things at once.
And this is the technique for returning multiple things, for calculating and for returning multiple
things at once.
So this question is very important.
So many companies ask this question, OK, so this question is very important.
Diameter of a binary mining company ask this question in their interviews so you should know how everything
is working.
So this is it from this video.
I will see you in the next one.