Welcome back.
Now in this video let's try to think about how we can solve this question.
We are given this binary tree over here.
And we have to find the diameter of this binary tree.
And remember we have seen that the diameter of a binary tree is the length between two nodes.
The longest path between two nodes and the length between two nodes is defined as the number of edges
between those two nodes.
All right.
Now, before we go ahead and discuss the algorithm about how we can solve this, let's make a few observations.
Now the first observation that we make is let's for example, take this node over here.
Now what is the diameter that passes through one?
Or for example, we are trying to think of the longest path that passes through one.
All right.
So for this let's go all the way left and let's go all the way right.
Possible.
Now over here we are taking the nodes seven and nine.
All right.
So the distance between these two nodes is equal to the number of edges in the path from 7 to 9.
So we are thinking of a diameter.
We know that the diameter is the distance between these two nodes.
But we can think of the same concept as the diameter passing through one.
Right.
So to find the diameter through one we went as far left as possible and as far right as possible.
Right.
So we have over here one edge.
And in this case we have 1234 edges.
So four plus one five would be the diameter that passes through this node.
All right.
So again over here this looks as if we are doing a depth first search.
Right.
So this must have something to do with DFS or depth first search.
So this is the first observation that we have made.
All right.
Now let's try to go bottom up and find the diameter at every node.
For example for node three we will only consider the things that are down.
That's why we are going bottom up right.
For example for node four we can't go anywhere down.
So we say that the diameter through four is zero.
Now for three we can go down here we have one and we have one over here.
So we can say that the diameter through three is equal to one plus one which is equal to two.
So we are going bottom up and we are finding the diameter at every node.
So let's try to do that.
So for these two nodes it's going to be zero right.
Because we cannot go down any further.
And for this node.
For node three, for the diameter through three we can go one depth over here.
Right.
So we have one edge over here and we have one edge over here.
So one plus one.
So that gives the diameter through node three is equal to two.
Right.
And what about the diameter through node two.
So we have one two over here.
Right.
So we have two over here.
So we can say this is equal to two right.
And we don't have anything to go right.
And for the node eight for this one over here we we have one two and three and one two and three.
So we can say that the diameter through node eight is equal to six right now.
Similarly for this node it's zero.
For this it's one.
And for this it's two.
Right.
And then for this node over here we can go one in this direction.
And we can go 123 and four in this direction.
So that would be one plus four which is equal to five.
Right.
And then for again for this node we can't go anywhere down.
So the diameter through that node is equal to zero.
Now in this way by thinking of the distance between two nodes we have, we have changed the way we thought
about it.
And instead of that we are thinking of the diameter through a particular node by going down both left
and right as deep as possible.
Right.
So in this way we have found the diameter at every particular node, so the diameter through every node.
And then we just take the maximum right.
So this would give us the diameter of this particular binary tree is equal to six.
So this is the second intuition right.
So instead of thinking instead of taking these two nodes and trying to think of the path through them,
we are actually thinking of taking the diameter through this node.
And then we found the diameter through every node.
And then we just take the maximum.
So this is how we are going to proceed with this.
So this is the second intuition.
All right.
Now let's proceed.
Now before we go ahead and think of how we can code this out or have an algorithm in a recursive manner.
For this, let's also quickly think about the height of a node.
All right.
So this is something that we have discussed previously.
But let me just quickly revise it over here.
The height of a node is nothing but the number of edges in the longest path from that node to the leaf
node.
So again we are going down right.
So from the node to the leaf node.
All right.
Now let's go ahead and write.
Try to think of the height of these nodes.
Now before that let me quickly revise.
The height of a leaf node is equal to zero.
Right.
So the height of these nodes which are leaf nodes is equal to zero.
And the height of a null tree is equal to minus one.
All right.
So below this you have null right.
So you have null over here everywhere.
So the height of those null levels is equal to minus one.
Because the height of a null tree is equal to minus one.
So these are two points that you need to keep in mind.
So again these three these 41234.
So we have four leaf nodes.
So the height over here is going to be zero.
All right.
Now what's the height over here.
And here it's going to be one.
Right.
So the height over here and here is equal to one.
And what is the height over here.
It's two right.
It's one two.
So the height over here is two.
And the height over here is also equal to two.
And what about the height over here that's going to be three.
And again the height over here is going to be four.
So we have just written down the height at every node.
Now when we compare the diameter and the height at a particular node, we can develop this intuition
that the diameter at a node is nothing but the height at the left node, plus the height at the right
node plus one plus one.
Let's try to understand this.
For example, let's take this node over here.
Now the height at the left node is zero, and the height at the life right node is equal to zero.
And then we have one edge over here and one edge over here.
That's why we have zero plus one and zero plus one.
So this this plus one plus one.
We are adding these two because we have two extra edges.
Right.
So that's these two edges in this case.
So we have the diameter of this one over here is equal to two zero plus zero plus one plus one which
gives us two.
Now let's try a few more cases.
What about this node over here?
Let's try to think of this node over here.
Now the height of the left node is equal to two.
The height of the right node is equal to two right.
So two plus two plus one plus one.
So we are adding these two right.
These two.
And we get the diameter over here which is equal to six.
Now we can see that mathematically this works.
Now let's also try to think of the intuition behind this.
Actually when we do this that is height of the left node plus height of the right node plus one plus
one.
What are we actually doing.
We are just taking the diameter through that node.
Right.
So we are going as deep as possible left which is this much right.
So height left plus one.
If we add these two that's the number of edges when we go as deep left as possible.
Now when we go as deep right as possible, we have to just take the height at the right node and then
plus one right.
Because we have this extra node.
So that is what we have done.
Right.
So when we wanted to find the diameter at a particular node, we went as much left as possible.
And then we go as much right as possible.
So that is nothing but this over here height at the left node plus height at the right node.
And then we have to add one plus one because we have these two edges over here.
So till here we get the height.
And then we have one over here till here we get the height.
And then we have one more edge over here.
So the diameter at a node is nothing but the height at the left node plus the height at the right node
plus one plus one.
All right.
Now so this is how we are going to solve this question.
All right.
And then again remember we have null nodes over here.
And the height at null nodes is equal to minus one.
So that is going to be our base case in the recursive solution that we are going to come up with.
All right.
So now let's proceed.
So let's try to go bottom up.
And then so we will have a recursive call recursive function.
So we will come till here.
And when we come over here.
And then we will go to its child which is null.
And then it will start returning.
So we will get minus one back from here.
All right.
So this is the intuition behind this solution.
So we will try to use this to come up with an algorithm to solve this question.
Now let's proceed and try to think of a solution in terms of the algorithm.
And remember when it comes to height right.
For for this to be able for us to be able to code this, we need a way to find the height at a particular
node and the height at a node at a particular node is nothing but the maximum between the height at
its left and right node, plus one right.
For example, if you want to know the height at this node, right?
So we just need to know the height the of the left node over here that's two.
And the height at the right node which is two.
So we take the maximum between these two and we add one.
For example if this was something like this we have eight.
Then we have let's say one we have two.
And let's say we have three over here.
And then we have four over here.
So the height over here is zero one and two.
And the height over here is zero right.
So if you want to know the height at this particular node we just need to take the maximum between these
two which is equal to two.
And then we have to add one because we are going one level up right.
So the height at this node will be just equal to two plus one which is equal to three.
So this is also something that we will use so that we can get the height at a particular node.
All right.
So let's now try to implement this solution using the intuition that we have developed over here.
All right.
So the diameter at a particular node is height at the left node plus height at its right child plus
one plus one.
And then we just need to find the maximum diameter.
And instead of thinking about the path between two nodes, we are just thinking of the diameter through
a node by going as much left as possible and as much right as possible, which is nothing but DFS or
depth.
First search.
All right.
So let's go ahead and write a function.
And let's just call it DFS.
Now if we encounter a node which is null then we will just return minus one.
So that is going to be our base case in our recursive solution.
And that is what will happen at this place right when we when we call the recursive call recursive function.
And when we get to the null node over here it will return minus one and then it will start returning.
So this is the base case.
And this DFS function is going to return the height.
Right.
Because at every point we want to get the height back so that we can find the diameter at that particular
node.
Right.
So this is also going to return the height.
And the height of a particular node is the maximum of the left height and right height plus one.
So we have seen that.
So this is what this function will return.
All right.
Now inside this function what we will do is we have we have called this function for a particular node.
Right.
So now we will try to find the height of its left child and right child.
All right.
So for this we will call this function recursively passing in the left child and the right child.
So we get the height at the left child and the height at the right child.
And then we are just going to implement this.
The diameter is going to be the sum of these plus one plus one.
So diameter of that particular node is LH left height plus right height plus one plus one.
So we get the diameter.
Then we need to check with the we need to have a global variable.
Let's just call it.
Max diameter.
All right.
Which we will initialize to zero.
And then whenever we calculate a diameter, we will compare that particular diameter with the value
that we have in max diameter.
So among these whichever is maximum that would be allocated to max diameter.
So in this way we will store the maximum diameter.
All right.
And then in this function we will just return the height of that particular node.
So this is how we are going to solve it.
And then finally when we are out of the function we will just return the maximum diameter because that
is what we need to find.
So let's proceed.
So we have seen how we are going to solve this question.
Now initially we will call this recursive function and we will pass the root.
So we will say DFS at root.
So we are calling the DFS function and we are passing the parameter root.
All right.
So we are over here.
Now inside this function we will check if this is null.
No this is not null.
So at this place we will call the DFS function recursively passing in the left node which is seven.
All right.
So this one over here.
Now again we are we are going to come inside this function.
We will see that this is not null.
So again we are going to call it for the left node.
And at this point we will see that it is null.
And hence this will return minus one.
So we get minus one minus one over here.
And similarly over here also we are going to get minus one right.
The right side also is going to return minus one.
So when we called the function with node seven its left height is minus one, its right height is minus
one.
And then the diameter at this particular node will be minus one plus minus one plus one plus one which
is equal to zero right.
So max diameter is equal to zero.
Initially we will initialize this to zero.
And at this point we calculate that the diameter is zero.
But over here also we have zero.
So we we do not need to overwrite this.
All right.
And then we proceed.
Right.
So this is done.
Now this was part of this left call right where we called the DFS function with node one.
So the left call will return right.
So the left call will return the maximum between these two which is minus one itself.
Plus one.
So over here we will get back the height of this which is equal to zero.
So this will return zero.
All right.
So that's part of the left call.
Now we will do the right call which is this one over here for node one.
So this will come over here.
And then from there it will go left all the way down.
And then when it comes over here it will return minus one right.
Minus one minus one.
And again from here we will return zero.
The same thing what we did over here.
So over here it will return zero.
And then from here also it will return zero because again this will return minus one.
This will return minus one.
And then the height of this will be the maximum between these two plus one.
Right.
So this will return zero.
So at this node we are going to get left height as zero and right height as as zero.
And then the diameter will be calculated as zero plus zero plus one plus one.
So we get that the diameter is equal to two.
And that will overwrite what we have already in max diameter because two is greater than zero.
So we get two over here.
All right.
So again from here we will return its height which is the maximum between these two plus one.
So we will return one.
And then over here we will return minus one because we have null.
Now again let's calculate the diameter over here one plus minus one which is zero plus one plus one.
So the diameter through two.
This node over here is equal to two.
So we don't need to overwrite.
And again from here we are going to return its height which is one plus one which is two.
Right.
So this will return two.
And that's how similarly from this part also you can see that again the height over here is also going
to be two.
Right.
So this also will return two.
And at this node when the left and right come back we will have two plus two plus one plus one which
is equal to six.
So that's how the maximum diameter will be calculated which is equal to six.
Again let's just trace this back.
You can see how it works first before it comes back.
It will go all the way down right.
It will go away this way.
Then it will try to go left but it will return minus one.
Then it will try to go right again.
It will try to go left.
This will return minus one again.
It will try to go right.
It will then try to go left which will return minus one.
And from here also you get minus one.
And you calculate the diameter over here which is going to be zero.
And then you return the height which is equal to zero right.
So from here you get back zero.
And this part over here gives back minus one.
So among these two the greater is zero plus one.
So over here we are going to return one.
And again you have minus one over here one over here.
The greater of these two is one and one plus one.
That's how you return two over here.
And that is how this function works.
And that's how we calculate the maximum diameter of the given binary tree.
All right.
Now let's quickly look at the complexity analysis of this solution.
The time complexity of this solution is going to be O of N because we are just doing depth.
First search over here.
Right.
And we have seen previously that the time complexity of DFS is nothing but O of N.
You can also think of it in this way.
We are just calling the DFS function on every node one time, right.
So again that's n number of calls.
And we are just traversing every node one time.
That's why the time complexity of this solution is O of n.
Now what about the space complexity.
Now this is a recursive solution.
So there will be space used up in the call stack.
So that's why we can say that the worst case space complexity is going to be O of n.
So this will happen when the given tree is not balanced right.
So when the tree is not balanced the height is going to be o of n, the height is going to be n if it
looks like a linked list.
Right.
So that's the worst case possibility.
So if the tree looks looks like just a link list, in this case the height is going to be n.
Otherwise if it's a balanced tree, we can say that the space complexity is going to be O of the maximum
depth or the height, because that's going to be the maximum number of calls which are there in the
call stack at the same time.