Sign in to watch this lesson
Algorithms - Trees and Range Queries · 4:48
Diameter and Farthest Distances
Hang a tree from any vertex and the lowest vertex is an end of a longest path; hang it again from there and the string between the two ends pulls tight into a diameter. We prove why the two sweeps work with a swap argument, see them break on negative weights where a tree DP joining the two deepest branches still works, and get every vertex's farthest distance from the diameter's endpoints or by rerooting.
You will learn
- Find a tree's diameter in O(n) with two breadth-first searches: farthest vertex a from anywhere, then the farthest vertex from a
- Explain the swap argument behind two sweeps, and why it needs non-negative edge weights
- Compute the diameter with a tree DP that joins the two deepest branches at every vertex, handling negative weights by clamping branches at zero
- Compute every vertex's eccentricity as max(d(v,a), d(v,b)) or by rerooting (down and up passes), and find the centres