wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> width and diameter of a binary tree
        
(Message started by: birbal on Mar 12^th, 2011, 8:21pm)

Title: width and diameter of a binary tree
Post by birbal on Mar 12^th, 2011, 8:21pm

What is meant by width and diameter of a binary tree?
How to find it ?

Title: Re: width and diameter of a binary tree
Post by towr on Mar 13^th, 2011, 1:18am

It seems that it varies what is meant. One definition for diameter is the longest path between two leaves; but that's also been called width occasionally. Another definition for width is the maximum number of nodes in the same level of a tree.

Title: Re: width and diameter of a binary tree
Post by birbal on Mar 13^th, 2011, 3:36am

on 03/13/11 at 01:18:23, towr wrote:

Max number of nodes at any level are very easy to find by doing a level order BFS traversal.

What about longest path b/w two leaf nodes?

Title: Re: width and diameter of a binary tree
Post by towr on Mar 13^th, 2011, 9:46am

For that you can do a depth first search. If you know how deep the left and right tree are, you know the longest path over that node in that subtree. So once you've passed through the whole tree, you'll know the longest path over any node.

Title: Re: width and diameter of a binary tree
Post by birbal on Mar 13^th, 2011, 11:46am

This should work i guess

Code:

int GetDiameter(Node *n)
{
if(n == NULL)
return -1;

int leftDiameter = GetDiameter(n->left);

int rightDiameter = GetDiameter(n->right);

if(leftDiameter+rightDiameter+2 > max)
max = leftDiameter+rightDiameter+2;

if(leftDiameter > rightDiameter)
return leftDiameter+1;

return rightDiameter+1;
}

Title: Re: width and diameter of a binary tree
Post by henrikk on Feb 19^th, 2012, 7:15am

diameter (T) = max ( diameter(T->left), diameter(T->right) , 1 + height(T->left) + height(T->right) );

Width(T) = maximum of nodes in a level

Title: Re: width and diameter of a binary tree
Post by frankrizal on Feb 19^th, 2012, 4:48pm

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.