**Find the maximum distance of a binary tree. The maximum distance or diameter is defined to be the number of nodes in the longest path inside a binary tree.**

C++:

01 int diameterTree(Node* head, int& d)

02 {

03 if(head==NULL)

04 return 0;

05 int left=diameterTree(head->left,d);

06 int right=diameterTree(head->right,d);

07 if((left+right+1)>d)

08 d=left+right+1;

09 if(left>=right)

10 return left+1;

11 else

12 return right+1;

13 }

02 {

03 if(head==NULL)

04 return 0;

05 int left=diameterTree(head->left,d);

06 int right=diameterTree(head->right,d);

07 if((left+right+1)>d)

08 d=left+right+1;

09 if(left>=right)

10 return left+1;

11 else

12 return right+1;

13 }

The above algorithm used post-traverse of a binary tree and calculate depth and diameter recursively. Note that, every node has been visited just once! So, the overall complexity is O(n).

Advertisements