Welcome back.
Let's now go ahead and write the function which we discussed in the previous video.
Let's call this function diameter binary tree.
Now this function is going to take in the root of the binary tree.
And let's say initially we say that the max diameter.
Is equal to zero, and we will return the max diameter at the end.
So this is how this function is going to work.
All right.
Now before we start to check for the diameter let's check whether the tree is a null tree.
So if the root is null we will just return zero at that point.
So if not root return zero right.
So if this is not the case we proceed further.
And over here we are going to write a function which we will recursively call.
And let's just say this is DFS because this is going to be depth first search traversal.
And this function is going to take in the node.
All right.
And then finally we are just going to call this function with the root node.
So this is how this is going to work.
So over here we will say DFS root.
All right.
Now let's try to complete this function once we are inside this function, when it is called with a
particular node, we will check if that node is null.
So if not node then we will just return minus one.
Again we have discussed this because the height of a null tree is equal to minus one for conceptual
purposes.
Now the height of a leaf node is equal to zero.
So again that's why the height of a null tree is equal to minus one.
And what we are going to do over here is we are going to find the left height.
So let left height.
Is equal to DFS.
And then we are just going to pass the left node.
So node dot left.
All right.
And the right height is going to be the same where we pass the node at the right side.
So right height.
Is equal to DFS node dot right.
And then over here we will have to return the height.
Right.
So again we are passing the left node and we want to get back the height.
Now over here we should get the height of the left node.
And this should be the height of the right node.
So this is again calling the same DFS function recursively.
So we can say that over here we will have to return the height right.
So the height of a particular node is nothing but the maximum among the height of the left node and
the right node plus one right.
Because the left node and right node are children, so they are one height less than that particular
node.
So we can say return math dot max among left height and right height plus one.
So this over here is the height of that particular node.
All right.
So again we have found the left height and and the right height by recursive calls.
Now the question asks us to find the diameter right.
So we have seen that the diameter is nothing but the sum of the left height and the right height.
And then we have to add one and one because there are two more edges.
Right.
So we can say diameter is equal to left height.
Plus right height.
Plus one plus one.
All right.
So these two we have seen in the previous video we are adding one and one because there is one edge
as we go up.
Right.
So this is the diameter for that particular node.
Now we are going to check whether this diameter is greater than the existing value in max diameter.
So we can say max diameter is equal to math dot max among the current value at max diameter and the
value that we just now calculated which is diameter.
So among these two, whichever is greater that value will be stored to max diameter.
And then we will just return this over here.
So this brings us to the end of this function.
So let's go ahead and call this function and see whether our code is working.
And then we will take a sample input and walk through the code.
So before we start and call this function let me just draw out this binary tree over here which we are
constructing so that we can easily visualize this.
All right.
So I have drawn the binary tree which we have constructed over here.
And now let's go ahead and call this function.
So diameter binary tree.
And we will just pass the root node which is tree dot root.
Now let's go ahead and run our code, and let's take a look at the output so we can see that we are
getting the output as six which is the maximum diameter.
So yes our code is working.
So that would be this.
Right.
So 123456.
So again let me just draw this out over here.
So this diameter six is actually the distance between these two nodes.
Right.
So we have 12345 and six six edges over here.
So that's why the maximum diameter is going to be six.
So this is working.
Now let's take this sample input which is this binary tree over here the root right.
So we are passing this root over here.
And let's walk through the code and take a look at what's happening over here.
So let's just go a little bit up.
So we have our function over here.
And it's now visible.
So this is the binary tree.
And this root is passed to it.
So let's now walk through the code and see what's happening.
So this root is passed to it.
Now we are inside.
Over here we are checking if the root is null.
No it's not null.
So we go ahead over here.
And max diameter is equal to zero.
So let's just trace that over here.
So max diameter at this point is equal to zero.
Then we come over here.
So this is just defining the function.
Then we come over here and we are calling the function with the root.
All right.
So we come over here the root node one is passed.
Now we come inside.
We check if the root if the node is null.
No it's not.
If it was null we would have returned minus one.
Then we come over here and we find the left height is equal to DFS node dot left.
So you can see we are going in this direction right.
So we are calling the same DFS function with this node over here again will come inside.
This will call it on this node.
In this way we will go in this direction.
So we will go depth first and we'll come over here.
Now this will call it on its child which is null.
And that will return back minus one.
Because for the case of null we are returning minus one.
So we are getting minus one over here.
And in this case the right also is null.
So that also will give back minus one.
And we calculate the diameter of this particular node which is minus one plus minus one plus one plus
one which is equal to zero.
So the diameter for this particular node is equal to zero.
And we are checking whether this or the existing value is greater.
So we don't need to swap because we already have zero and we're just getting zero over here.
All right.
And then we are done with this call.
Right.
For this call we are done with the left and the right.
And over here we are going to return the maximum between these two plus one.
So these two are equal.
So we are just going to return minus one plus one right.
So we are going to return from here the height as.
Minus one plus one, which is equal to zero.
So the height zero is going to get returned over here.
So this was part of the left call of this particular node.
Right.
So the left call is done.
When we do the right call for this node we will get back minus one because we have null over here that
will return minus one.
All right.
So diameter in this case will be zero plus minus one which is minus one plus one plus one.
So that that gives us one right.
So we can see that the diameter over here is equal to one.
And that's just the distance between these two nodes.
Because we have one edge over here now because one is greater than what we have existing zero.
Right.
So we have to replace this with one.
And then we come over here.
We are going to return the max between 0 and 1, which is zero plus one.
So from this we are going to return one.
All right.
And again seven on its right it has null.
So that part is going to return minus one.
Now we again calculate the diameter which is one plus minus one which is zero plus one plus one which
is equal to two.
Right.
So the diameter of this node is going to be two which is greater than one.
So we replace that over here which is happening over here right in this line.
And then from here we are going to return the maximum between the left height and the right height.
Over here we have one.
And over here we have minus one.
So one is the greater one.
So one plus one.
So over here we are going to return one plus one which is two right.
So again you can see that this is the height of this.
Right.
So one two.
So that's the height of this node.
And we are returning the height.
So two we are getting two from here.
And in the same manner from this side also because we can see visually it's going to be the same right
over here.
It's the height.
The height is zero.
The height is one the height is two.
So over here also we are going to return two.
Again.
It will go all the way down and then it will come back because this is a recursive call.
So at this point we will get two from both the sides and two plus two because over here we have one
plus one right.
So two plus two which is four plus one plus one will give us six.
And that will be the maximum diameter.
And that is what we have.
We have seen that the function returns the function returns the maximum diameter.
So that's how.
Now let's just complete tracing this part.
So for node three the left call is done.
So this line is done.
Now we go to the right call which will go in this direction right now.
At this point again it will try to go left.
And this will return minus one for this node.
Right.
So the height the height over here is going to be minus one.
Because for the height of a null tree is minus one, the same thing will happen again.
It will go right.
So from here it will go right which.
And then from here it will try to go left, but it will return minus one.
Because we have seen that if the node is null, we will return minus one as the height.
And then again from here it will go right.
And you can see that over here it will try.
Go left minus one will be returned.
It will try.
Go right again.
Minus one will be returned.
So the diameter would be calculated as minus one plus minus one which is minus two plus two zero.
So the diameter of this node is equal to zero.
And then we are going to return the maximum between these two which is minus one.
And then we are going to add one right.
So we are going to add one.
So we are going to return zero.
So over here in for for this call it's going to return zero.
So at this node we are getting minus one and zero right.
So again it will calculate the diameter which is not going to be greater than what's there.
Right.
So just let's just calculate it.
So we get minus one plus zero which is minus one plus one plus one.
So we get one.
So the diameter of this node is just one.
Right.
And then it's going to return the height which is the greater of these two which is zero plus one.
So from here we are going to return one.
And again the height from here what will be the height.
It will be the greater of these two which is minus one and one.
The greater is one plus one.
So that's how we are going to get back two over here as well.
So at this node this the left gives back to the right also gives back to.
And then we add two.
So that's how we get six which is the diameter.
So this function works in this way.
And then again we have seen that over here we have the height.
The height is the greater of these two which is two itself plus one.
So this will return three as the height.
And from the left side this will return zero.
And then again at this point the diameter will be three plus zero plus two which is equal to five.
So we can see that we have 1231234.
And then this node right 12345.
So that's how we get five which is the diameter through this node.
In this way we have found that the diameter of the given binary tree is equal to six.
Now let's take a quick look at the space and time complexity of this solution.
Now over here we are just doing DFS.
And we know that the time complexity of DFS is O of N, because we are just traversing through every
node one time.
Or you can say that we can we are we are recursively calling the DFS function once for every node.
So the time complexity of this solution is going to be O of n.
And the space complexity will depend on the depth of the tree.
So the space complexity is equal to the maximum depth of the tree because this is going to be a recursive
solution.
Now this because we are doing Big-O analysis.
The maximum possible depth is going to be O of N, right?
When the given binary tree is just going to look like a linked list.
So that's why we can say that the space complexity of this solution is also o of n.