whats the complexity to find diameter?
Help understand the time complexity
@mayankA47 If you find the diameter of a tree using preorder traversal , it would have a complexity of O(n^2) as for every node, we would have to calculate height and computing height is of O(n) making the complexity O(n^2). In this approach, we are not storing height of any node but we are computing it for each node which makes it time inefficient.
Another efficient approach to compute diameter of a tree is by bottom up traversal or by post order traversal which would have a complexity of O(n).In this approach, we will begin from the leaf node and store heights while traversing the tree.For every node we will return height of that node and diameter of that node. These stored heights and diameter will help in computing the height and diameter of the parent node.
For more clear understanding, please refer the lecture videos on it. It is clearly explained there.
Hope this helps.
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.