1
$\begingroup$

This is NOT HW, this is from Skienas book, and I just couldn't solve it at all.

Please give me a hand here, in understanding and solving it, thanks.

Let G = (V, E) be a binary tree. The distance between two vertices in G is the length of the path connecting these two vertices, and the diameter of G is the maximal distance over all pairs of vertices. Give a linear-time algorithm to find the diameter of a given tree. (*)

I figured I'd do a DFS, and increment on each node in terms of the depth of the tree

Improve this question
$\endgroup$
2
  • $\begingroup$ Hint: What happens if you do two BFSs? Pick an arbitrary vertex $v$, find a vertex $u$ as far away from $v$ as possible. If you do a BFS from $u$, which vertex will you find to be farthest away from $u$? $\endgroup$
    – Pål GD
    Apr 21 '13 at 19:55
  • $\begingroup$ Find an answer here. $\endgroup$
    – Raphael ♦
    Apr 21 '13 at 23:03