Jun 122012

Diameter of a tree is the longest path (Number of nodes) between two leaf nodes of the tree. It is also called width of the tree.

For example, diameter of the below tree is 6 (red color nodes form part of the diameter)

A / \ B C / / \ D E F \ G

Note that the diameter may not, necessarily include the root of the tree.

### Solution:

At any given time the diameter of the tree (or sub-tree) is the largest of the following:

- Diameter of Left sub-tree (does not include current root in diameter)
- Diameter of Right sub-tree (does not include current root in diameter)
- The longest path that goes thru the root of tree = Height of LST + Height of Right Subtree + 1 (For the root)

The below code returns the diameter. It uses a helper function to compute the height of the subtree at any level.

**Code:**

/* Returns the diameter of a binary tree */ int diameter(Node * root) { if (root == 0) return 0; // Get the height of left & right sub-trees int lh = height(root->lptr); int rh = height(root->rptr); // Diameter of left and right subtrees recursively int ld = diameter(root->lptr); int rd = diameter(root->rptr); return max( (lh+rh+1), ld , rd ); } // Function to compute the height of a Binary tree int height(Node* root) { if(root == NULL) return 0; return ( 1 + max(height(root->lptr), height(root->rptr) ) ; }

### 2 Responses to “Diameter of a Tree”

Comments (2)

Nice solution

thanks sai ðŸ™‚