## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
Can some body tell how to calculate the diameter of a binary tree
diameter of a binary tree is maximum horizontal spread of the tree , that is maximum number of nodes present at any level
Topi Wednesday, April 11, 2007
Is'nt the diameter the largest of all shortest paths in the tree.....
Topi Wednesday, April 11, 2007
Well i am confused abt what is meant by the diameter of a tree.So please explain it as well.
Topi Wednesday, April 11, 2007
Breadth first traversal. One extra pointer for next level, and count the number of nodes at each level.
Jim Wednesday, April 11, 2007
Diameter of the tree is the length of the longest path.
Usually in graphs diameter is defined as the longest shortest path. i.e for each pair of vertices (u,v) find the shortest path. Now pick the largest among all pairs. In case of a tree, since there is only one path between any two vertices, diameter equals the longest path. An algorithm: Root the tree at any node. Find the deepest node, say R. Now re-root the tree at that node and find the deepest node say RD. The path from R to RD gives the longest path.
Tapori,
I did not get what you are saying. What do you mean by re-root at "that" node. Do you mean to say that again find a path from root to some different node RD? Is finding longest path among all the paths present in a tree solution to this question? Then this is similar to finiding Height of the tree? Please clarify.
int diameter(Tree* t)
{ if (t == NULL) return 0; int leftDiameter = diameter(t->leftChild); int rightDiameter = diameter(t->rightChild); return (max(leftDiameter, rightDiameter) + 1); }
brucesea Wednesday, April 11, 2007
Tapori can you write the pseudo code for this and can
you please cite an example.I am still unclear about it. Thanks
Ramesh Thursday, April 12, 2007
Assume we are given the tree with links to neighbours.
Rooting a tree at R means: consider R as the root node. Its neigbours become children of the root node and so on. So basically the algorithm is: given the current root r, find the max depth node, say R. Now root the tree at R. Now find the max depth node in the resulting tree. Let that be RD. The R to RD is the longest path. Sorry, I am not sure if writing pseudo code will help. Maybe some else can do it if they feel like it.
Sorry that I mis-understood the question.
void diameter(Tree* t, int& depth, int& dia) { if (t == NULL) { depth = 0; dia = 0; return; } int leftDepth, rightDepth; int leftDiameter, rightDiameter; diameter(t->leftChild, leftDepth, leftDiameter); diameter(t->rightChild, rightDepth, rightDiameter); depth = max(leftDepth, rightDepth) + 1; dia = max(leftDiameter, rightDiameter, leftDepth + rightDepth + 1); }
brucesea Thursday, April 12, 2007
@brucesea
can u please explain with an example . I am still confused abt the diameter. Please tell it with one example of BST.Like taking some values.Thanks a lot
Pupil Thursday, April 12, 2007
Pupil,
You can access following page to understand the meaning of Tree Diameter. http://www.cs.duke.edu/~ola/courses/cps100spr96/tree/trees.html
brucesea Thursday, April 12, 2007
Thanks .
But I need a working example to understand and then i can relate your algo to it. Just with some data.
Pupil Thursday, April 12, 2007
Pupil,
The webpage I mentioned already provides a good example about the meaning of "Tree Diameter". Following diagram shows two trees each with diameter nine. http://www.cs.duke.edu/~ola/courses/cps100spr96/tree/diameter.xbm
brucesea Thursday, April 12, 2007 |

Powered by FogBugz