also please help me with how does the time complexity is calculated in recursion… its not clear from video
Please expain how the time complexity is reduced to O(N)
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. Since this is just a postorder traversal, so complexity is O(n)
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.