This can be solved in a better way. Also, we can reduce the time complexity to O(n) with a slight modification in the data structure and using an iterative approach. For a detailed analysis and multiple ways of solving this problem with various data structures.
Here's a summary of what I want to explain in a blog post of mine:
Recursive Approach – Tree Diameter
Another way of approaching this problem is as follows. As we mentioned above that the diameter can
- completely lie in the left sub tree or
- completely lie in the right sub tree or
- may span across the root
Which means that the diameter can be ideally derived by
- the diameter of left tree or
- the diameter of right tree or
- the height of left sub tree + the height of right sub tree + 1 ( 1 to add the root node when the diameter spans across the root node)
And we know that the diameter is the lengthiest path, so we take the maximum of 1 and 2 in case it lies in either of the side or wee take 3 if it spans through the root.
Iterative Approach – Tree Diameter
We have a tree, we need a meta information with each of the node so that each node knows following:
- The height of its left child,
- The height of its right child and
- The farthest distance between its leaf nodes.
Once each node has this information, we need a temporary variable to keep track of the maximum path. By the time the algorithm finishes, we have the value of diameter in the temp variable.
Now, we need to solve this problem in a bottom up approach, because we have no idea about the three values for the root. But we know these values for the leaves.
Steps to solve
- Initialize all the leaves with leftHeight and rightHeight as 1.
- Initialize all the leaves with maxDistance as 0, we make it a point that if either of the leftHeight or rightHeight is 1 we make the maxDistance = 0
- Move upward one at a time and calculate the values for the immediate parent. It would be easy because now we know these values for the children.
At a given node,
- assign leftHeight as maximum of (leftHeight or rightHeight of its left child).
- assign the rightHeight as maximum of (leftHeight or rightHeight of its right child).
- if any of these values (leftHeight or rightHeight) is 1 make the maxDistance as zero.
- if both the values are greater than zero make the maxDistance as leftHeight + rightHeight – 1
- Maintain the maxDistance in a temp variable and if in step 4 the maxDistance is more than the current value of the variable, replace it with the new maxDistance value.
- At the end of the algorithm the value in maxDistance is the diameter.