Author |
Topic: width and diameter of a binary tree (Read 4945 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
width and diameter of a binary tree
« on: Mar 12th, 2011, 8:21pm » |
 Quote  Modify
|
What is meant by width and diameter of a binary tree?
How to find it ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: width and diameter of a binary tree
« Reply #1 on: Mar 13th, 2011, 1:18am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: width and diameter of a binary tree
« Reply #2 on: Mar 13th, 2011, 3:36am » |
Quote Modify
|
on Mar 13th, 2011, 1:18am, towr wrote:| 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. |
|
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?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: width and diameter of a binary tree
« Reply #3 on: Mar 13th, 2011, 9:46am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: width and diameter of a binary tree
« Reply #4 on: Mar 13th, 2011, 11:46am » |
Quote Modify
|
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;
}
|
|
|
| « Last Edit: Mar 13th, 2011, 11:47am by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
henrikk
Newbie
Posts: 2
|
|
Re: width and diameter of a binary tree
« Reply #5 on: Feb 19th, 2012, 7:15am » |
Quote Modify
|
diameter (T) = max ( diameter(T->left), diameter(T->right) , 1 + height(T->left) + height(T->right) );
Width(T) = maximum of nodes in a level
|
|
IP Logged |
|
|
|
frankrizal
Newbie
Gender:
Posts: 23
|
|
Re: width and diameter of a binary tree
« Reply #6 on: Feb 19th, 2012, 4:48pm » |
Quote Modify
|
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print