Hi, everyone.
So in this video, we are going to discuss and find the diameter of a binary tree.
So what is the meaning of diameter?
So encircle?
Diameter is basically the maximum distance between any two points, so similarly, in case of binary,
diameter is the maximum distance between any two nodes.
So let us take one example.
So this is a binary tree and what is the distance between this node and this node?
So count Edwyn as two and three.
So the distance is basically three.
And this note and this note, the circumstances, one, two, three and four, so the distances for
but I need to find out the diameter and diameter is the maximum distance between any two roads.
So the maximum distance will be between this node and this additional.
So count one, two, three, four and five.
So the answer is five.
Now, there are many ways in which we can obtain five.
For example, the distance within this node and this node is also five.
The distance between this node and this node is also five.
So there are many ways to achieve this number five.
But since we only want to return the integer so we do not care about the number of combinations, we
just want to return the diameter and diameters, the maximum distance between any two node.
So for Destry.
My output will be five.
So how we can solve this question, so let's take one more example first.
So if this is a binary tree.
What is the maximum distance for this diameter?
So one, two, three and four, so the diameter is four and we can see we can say with this diameter,
diameter is left eight plus right height.
So left out is two.
And right now it is also two.
So two plus two is four.
So let's take one more example.
So for this binary tree vertebrae, the diameter.
So diameter is between this node and this node.
So one, two, three, four and five.
So diameter is coming out to be five.
And what is left, right, so left out is to what is right.
So right now it is three.
So two plus two is five.
So can we say that this formula is correct?
So I think this is a good guess, but this formula is not correct.
Why?
It is not correct.
So I will give you one example.
This formula will not always work.
It will work only in some situations.
So if this is Maitri.
So for this Pinetree.
What is left out, right, right, right, right is one.
And left is one, two, three and four, so four plus one is five, so according to this formula, my
diameter should be five.
But let's see whether that's correct or not.
So I think it is not distance between this note and this note.
So one, two, three, four, five and six.
So the correct answer is basically this.
So in this problem, in case of this binary tree, this one is not correct.
So this is a very good guess.
But this is not correct.
This is not the correct way of finding the diameter.
So in this case, the diameter is not passing through, the diameter is not passing through the route.
And I never said in the question that diameter must pass through root.
So it is not necessary that diameter must pass through root.
So what are the situations that we can have?
So there are three situations, according to me.
So first one is basically how we will utilize our tree so we will regulate our tree like this.
Now, one situation is the first note lies in the left, the second northerlies in the right supply.
So in this case, our answer is correct.
So diameter will be left eight plus right out.
Now, if both the nodes lie in the left Sabry so if both an old line, the leaves are so right it doesn't
have any effect.
So in this case my answer will be left diameter.
So left diameter is the diameter of the whole tree, so diameter will be the diameter of the hole.
So this is whole the diameter because both the nodes lying in the left and right subtree has no effect.
Now if both the nodes are present in the right subtree, so in this case, my answer will be the right
diameter because diameter does not have any effect, because the left tree does not have any effect.
So in this case, the right diameter will be the whole tree diameter.
There are two situations.
So first one is basically our tree will be like this.
So if this is Maitri.
Then the second situation, military can be like this.
And in the third situation, my dream can be like this.
So for this kind of free for distri, my answer is basically left out, plus right out.
So basically this thing.
Left, right, right, right.
So this will be the time for this kind of tree, my answer will be the left diameter monster will be
the diameter for this tree.
My answer will be the right diameter.
So what we need to do.
So we'll find out all this value.
So this is our first option, this is our second option and this is our third option and our answer
will be the maximum of the three options.
So make them our first option, second option and third option, simple and how we can find out the
diameter we will colocation for finding out the diameter.
Similarly, we will call the for finding out the right diameter.
And that will be my answer.
Simple.
So this question is basically present only it could find the diameter of a binary tree and now let us
compute the cord for this function.
So we are taking root as input.
First of all, we need to discuss about the best case, so what is the best case if the route is.
So if rotational, what is their diameter, diameter will be zero, simple maximum distance between
any two nodes and in my tree I don't have any node, so diameter will be zero.
So our first option is basically.
This one, left, right, plus retied.
So left out, right, right.
So I will write the code for this hate function.
I will give the left subtree.
And I will give.
The right subtree.
So I will write the code for this function, how to function.
So our first option is very simple.
Left, right plus right now our second option is.
I was separate option is left Daym and third option is right diameter.
So our option to.
It's basically Dimitrov by Nutri.
And we will give it left subtree.
And our third option is.
The right diameter, so we'll call this function.
And we will give it.
The right subtree.
And now what we need to do.
So we need to lay the Maximov first option, second option and third option, so we have inbuilt max
function, so we will use it.
So Maximov.
N.B. This is how it works.
It will take two things as it put to argument as input.
And I want to take the input of two things.
So I will write like this mix of a mix of BNC.
So this is how we can take the maximum of three things.
So let's write the code.
So I will return.
The maximum of.
Option one.
Mix of option two and three, option two and option three.
So the only thing left is basically to write the code for this function, so let's write the code.
Will teacher, then the function is height.
So this will take root and put.
And redecide, so if.
Rotational.
My height is zero, if true, does not exist Diatta zero, otherwise the height will be one plus maximum
of left and right out.
One plus maximum of left out.
And right, right.
So, yes, I think our gold will rock solid right now, and then we will submit.
Now, there are some rhetorical.
So basically, our goal is working and now we will discuss the time, complexity for our solution,
relative time, complexity.
So first, let us discuss about the time, complexity of the function.
So let's discuss about the to function.
So what we are doing.
We are calling it a collision on the left and on the right separately, so this is Natalie.
So I will call it function for the left subtree, I will call it function for the right.
So basically we are going to each and every node and for each node we are doing a constant amount of
work.
So for each node we are doing.
So this constant amount of work, one plus.
So this is also the constant amount of work.
So we are going through each and every node and for each and what we are doing, constant amount of
work.
So that time complexity for how it function is big often.
Now, let's try to find out the time, complexity of this function diameter function.
So, again, what we are doing.
So this is Maitri.
So we are calling their diameter function on the left.
We are calling diameter function on the right.
So I am calling diameter a function for the left subtree.
I am calling diameter function for the right subtree.
So we are going to each and every node and let's see at each and how much amount of work we are doing.
So this is constraint, the amount of work and then we are calling the function for every node, we
are calling the function for every node and this is the constant amount of work.
So basically for each node, I'm calling the function.
So now let's try to find out the complexity of this function.
So basically three can be of two types.
So first three can be balanced.
So this is an example of a balanced tree.
The number of nodes in the left and the right are they both are the same.
So I'm standing here at the root node and then what I'm doing.
So for each node, I'm calling the function.
So if there are any node, so for each and what I am calling the function so.
Gay and minus one, or we can simply write it again.
Plus, we are doing some constant amount of work for each a..
OK, so this constant so we can remove it and then what we are doing, so we are calling the function.
For delectably and for the rights Sabry, so two times.
And by do OK, now we have seen this, so we have seen this somewhere, so this is exactly like.
So this is.
Exactly like Mozart.
So what is your time, complexity, so time complexity is and Logan.
Now, another kind of tree that we can have is basically this kind of tree.
Now, let's try to find out the complexity of this function for this type of.
So initially we are standing here at the root node, then I am calling.
So this is constrained amount of work.
So let's try to their number of nodes is.
And so this constant amount of work or we can remove it since it is constant, then we are calling the
hate function.
So left simply does not exist and the right subtree.
So how many number of nodes are present and minus one node.
So I am Complexo and minus one time complexities and minus one in tookey simple Hyett function time.
Complexity was linear if you remember so and minus K and then what we are doing.
So we are calling the function on the left subtree.
We are calling the function the right subtree.
So left are Presnell and the rights are pre how many notes are there and minus one nodes are there.
So this is the Rickerson deletion.
So this is direct resolution.
Now, what would be the time, complexity, so how we can solve this?
So let's take the example of the bubblehead.
So in the world sort.
What we do, so we compare the elements and we still have them, then we compared the elements and we
swab, we compared the element and we'll swab.
So after one iteration.
The largest element will represent at last.
So after midnight, that means after End-Time big oftentime, the largest element will be present at
last.
So we have to do this same thing for and minus one element we have done once.
And it cost me big oftentime.
I have to do the same thing for the remaining and minus one element.
So what is the solution?
So for one element, you did big oftentime.
And we need to do the same thing for nd minus one element also so and minus one.
So now you can compare so and minus one it took, it seems.
And so the reconciliation is the same.
And what is your time complexity for the short term?
Complexity is and square.
So for this type of tree, the time complexity is and square.
So let's write everything again.
So we can have two kinds of free.
So this is the first one, which is the balanced number of free number of nodes in the left, Sabry
is equal to the number of nodes and the right subtree.
And this is another kind of reach that we can have.
So for Destry, the time, complexities and log-in, for distri, the time, complexities and Scribd.
So what is the correct term complexity, so our role is we will report the worst case time complexity.
So ideally we should say the time, complexities and square, because this is the worst case, time,
complexity.
But we will not write our answers and square because if we see for this kind of three.
We can do the calculation and we can find out the height is basically log often where any number of
nodes log often.
And for this tree, there is no need to do any calculation for finding out the height.
Height is simply the number of nodes present.
So what is the time, complexity?
Time is basically in multiply the height, Logan is basically the height for this type of reform.
Balestra.
So here the time complexities, number of nodes multiply by eight and here the time complexities and
multiply by height and how it is and.
So my correct term complexity is basically big off number of nodes multiplied by hate.
So this is the correct time complexity that we will report number of nodes multiplied by HAID.
So what we want to do so in the next we do, we want to remove this, we want to decrease our time,
complexity, and by the time complexity is high, let's try to analyze why the time complexity for this
function is high.
So let's take one example.
So if this is Maitri.
One, two, three and four.
So I am standing at this node, so what I will do, I will say find out for the left does not exist.
So finally, hired for the right one will call on to give me the right.
So I want to find the out of when no one will ask her to give me the hate.
So we will find out ASAP and it will return the answer.
Simple.
So now option two so left does not exist.
So option three daym so haven, give me your diameter.
So when will call on two and in two we are again we will again call the hate function so four two two
will ask for it again.
So see when I am calling this function for two then two will call hate again.
We will again ask for hate.
So you can see we are doing repetition of the same work.
We are doing the same work multiple times.
So number of calls for two will increase, similarly, there will be more calls for this note, there
will be much more call for this.
So the time complexity is big off and multiply by eight by the time complexity is more because we are
doing the same work many times.
And that is the reason, so how we can improve our time complexity.
So what we will do?
If this is.
Mitry So I will ask her to give me the heightened diameter at once.
So to Willetton, height and diameter at once.
OK, we will not call multiple time, so here what we are doing, first of all, I am asking so if this
is the three.
So for one, for one, I want to find out the hate for when I find out the hate, so I want you to give
me the hate.
So when will call on two for finding out the hate?
So when I am the function of two, so two will again call on three hate, three give mediate or two
will call on three to give it tight.
Now, when you want to find out the diameter of one, so you want to find out the diameter of one,
so one will call on to here to give given a diameter, we will again call for finding out the height.
So we will again.
So we are again finding out the height and for finding out who will again call on three and three will
return the height.
So we are doing the same work multiple times and that's why the time complexity is more so.
What I want to do is I'm giving you a hint.
So what I will do so in this approach, first we are asking here to give me the height.
So once to give the height, then I will ask again here to give me the diameter.
First I am asking for to give me the height.
Then I'm asking to again to give me the diameter.
OK, so one is calling on two.
Here to give me the height, so went to Willetton, the height, then I am again calling on to find
the diameter.
So that's why the repetition of work will be there and then to Willetton, the diameter.
So what I want to do is I will call in such a way.
So I will call like this here to give me the height and diameter at once.
So too will do the calculation.
Only one, only once.
And to Willerton both values and height and diameter both.
So that's how we'll be able to solve this question and less time complexity so correctly, our time
complexities and multiply by each.
So we want to remove we want to decrease our time complexity.
And this is the way that we will reduce our time complexity.
So in the next we do we will discuss about it and we will also write the code.
So this is it from this video.
I will see you in the next one.