RSS Feed

techInterview Discussion

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

Is'nt the diameter the largest of all shortest paths in the tree.....

Well i am confused abt what is meant by the diameter of a tree.So please explain it as well.

Breadth first traversal. One extra pointer for next level, and count the number of nodes at each level.

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);
}

Tapori can you write the pseudo code for this and can
you please cite an example.I am still unclear about it.

Thanks

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
 
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,
You can access following page to understand the meaning of Tree Diameter.
http://www.cs.duke.edu/~ola/courses/cps100spr96/tree/trees.html

Thanks .

But I need a working example to understand and then i can relate your algo to it.

Just with some data.

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