Definition : Diameter of a tree is the longest path between two leaf nodes in a tree.
We can see in the picture below that Diameter of the tree would be maximum of these:
i. Diameter of left subtree.
ii. Diameter of right subtree.
iii. Path that goes through the root i.e. height of left subtree + height of right subtree + 1
int diameter(struct node *root) { if(root==NULL) return 0; else { int leftH = height(root->left); int rightH = height (root->right); int leftD = diameter(root->left); int rightD = diameter(root->right); return max(max(leftD,rightD),leftH+rightH+1); } } int height(struct node *root) { if(root==NULL) return 0; else max(height(root->left),height(root->right))+1; }
Time Complexity : O(N^2) as time complexity of height function is O(N) and we are calling it for every node.
Optimized solution: We can reduce the time complexity to O(N) by calculating height in the diameter itself and don’t call height recursively for each node.
int diameter(struct node *root, int* height) { int leftH = 0, rightH = 0; int leftD = 0, rightD = 0; if(root == NULL) { *height = 0; return 0; } leftD = diameter(root->left, &leftH); rightD = diameter(root->right, &rightH); *height = max(leftH, rightH) + 1; return max(leftH + rightH + 1, max(leftD, rightD)); }