Find diameter of a binary tree

Given a binary tree, write an efficient algorithm to compute the diameter of it. The diameter of a binary tree is equal to number of nodes on the longest path between any two leaves in it.

 

For example, below figure shows two binary trees having diameter 6 and 5 respectively (nodes highlighted in blue color). The diameter of binary tree shown on left side passes through root node while the diameter of binary tree shown on right side do not passes through the root node.

diameter-of-binary-tree

 


 

Simple solution would be to calculate height of left subtree and right subtree for each node in the tree. The maximum node path that passes through a node will have value equal to sum of height of its left and right subtree plus 1. Finally, the diameter is maximum among all maximum node paths for every node in the tree. The time complexity of this solution is O(N2) as there are N nodes in the tree and for every node we are calculating height of its left subtree and right subtree that takes O(N) time.

 

We can solve this problem in linear time by doing post-order traversal of the tree. Instead of calculating height of left subtree and right subtree for every node in the tree, we can get the height in constant time. The idea is to start from the bottom of the tree and return height of subtree rooted at given node to its parent node. The height of subtree rooted at any node is equal to 1 plus maximum height of the left subtree or right subtree. We pass diameter by reference to the function (instead of returning it) and update its value within the function itself using left and right subtree height.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
 


 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz