techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Binary Tree Question

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 Send private email
Wednesday, April 11, 2007
 
 
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.
Niks Send private email
Wednesday, April 11, 2007
 
 
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.
Tapori Send private email
Thursday, April 12, 2007
 
 
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
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz