# LInear time algorithm to find the diameter of a tree [duplicate]

This question already has an answer here:

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

## marked as duplicate by Raphael♦Apr 21 '13 at 23:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 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$? – Pål GD Apr 21 '13 at 19:55
• Find an answer here. – Raphael Apr 21 '13 at 23:03