Diameter of binary tree Recursive implementation

Diameter of binary tree

We all know about height of a binary tree. Diameter of binary tree is closely related to height of it. Problem statement is: Given a binary tree, find diameter of binary tree. Diameter of binary tree is maximum distance between any two nodes in tree. Path between two such nodes may or may not pass through root of the tree. For example, diameter of following trees will be 4 and 7 as shown

diameter of binary tree examplediameter of binary tree

Find diameter of binary tree

As I said in start diameter is closely related to height of binary tree. If Diameter includes root node, then diameter is summation of height of left sub tree and right sub tree plus one for root. If diameter does not include root, then diameter is either diameter of left sub tree or right sub tree.

At any given node, check if diameter of any subtree below tree is greater than sum of height go left subtree, right subtree plus 1. If that is the case, diameter of entire tree remains diameter of that subtree, else change diameter to height of left subtree + height of high subtree +1. Actual expression of diameter of a tree at rooted any given node is

MAX(height(left subtree) + height(right subtree)h+1,
     MAX(diameter of left subtree,diameter of right subtree ));

Starting with leaf nodes we traverse up the tree and pass diameter value for each node to parent node. At parent node, decide whether to include this node based on above mentioned condition.

Algorithm to find diameter of binary tree

1. Start from root
2. If there is left child of node, find diameter of left child.
3. If there is right child, find diameter of right child.
4. Find height of left sub tree.
5. Find height of right sub tree.
6. Return maximum of 1 plus height of left sub tree plus height of right sub tree,  diameter of left sub tree, diameter of right sub tree.

Diameter of binary tree implementation

Since each node of tree will be traversed, complexity of algorithm to find diameter of binary tree will be O (N) where N is number of nodes in tree.
Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us and earn for yourself.