Tree Diameter & Center

The diameter of a tree is the longest distance between any two of its vertices. In the lecture’s tree it runs from 13 to 10 through 12, 8, 5, 2, 1, 3 and 6: 8 edges. A tree can have more than one diameter (a Y shape with three equal arms has three), but they all have the same length.

The lecture’s first observation is a lemma: both ends of a diameter are always leaves. Proof by contradiction: suppose an end V of a longest path were not a leaf. Then V has a neighbour off the path, and one more step gives a path longer than the longest one. Contradiction.

Brute force would run BFS from every vertex and keep the largest distance seen: O(V²). The next two sections bring it down to O(V).

The theorem turns straight into an algorithm:

• run BFS (or DFS) from any vertex and take the farthest vertex V: by the theorem it is one end of a diameter;
• run BFS again from V; the farthest vertex U is the other end, and d[U] is the diameter.

On this tree, starting from 7: the first BFS reaches 13 at distance 7, the farthest, so V = 13. The second BFS from 13 reaches 10 at distance 8: U = 10, diameter 8. Keep the parent array of the second run and you can print the path itself: 13, 12, 8, 5, 2, 1, 3, 6, 10.

Careful: the first distance (7) is not the diameter; it only tells you where to start the second run. Each BFS is O(V) on a tree, since E = V − 1, so the whole algorithm is O(V). With non-negative edge weights, replace BFS by a DFS that sums the weights; the theorem still holds.

Leaves always have a larger eccentricity than the inner vertices, so they can never be the center (unless the tree has at most two vertices). The lecture’s algorithm: remove all leaves at once, together with their edges. What remains is again a tree; repeat until one or two vertices are left. Those are the centers.

Implementation: keep the degree of every vertex, put all leaves (degree 1) in a queue, and process round by round. Removing a leaf decrements its neighbour’s degree, and a neighbour whose degree drops to 1 becomes a leaf of the next round. O(V).

On this tree: round 1 removes the six leaves 4, 7, 9, 10, 11, 13; round 2 removes 6 and 12; round 3 removes 3 and 8; round 4 removes 1 and 5; vertex 2 remains. The diameter, the longest path, survives the longest, which is why the center lies on it: an odd number of vertices on the diameter gives one center, an even number gives two.