Tree Center

The center of a tree is the vertex (or the two adjacent vertices) minimising the maximum distance to any other vertex. Rooting at the center gives the smallest possible height, and it is the canonical root when a tree must be compared or hashed.

A tree has exactly one or two centers. Two centers occur precisely when the diameter has odd length (an even number of vertices on the path).

Method 1: leaf peeling — $O(n)$

Repeatedly strip the current layer of leaves, like peeling an onion. What remains at the end is the center.

vector<int> treeCenters(int n, vector<vector<int>>& adj) {
    if (n == 1) return {0};
    vector<int> deg(n);
    vector<int> layer;
    for (int i = 0; i < n; i++) {
        deg[i] = adj[i].size();
        if (deg[i] <= 1) layer.push_back(i);
    }
    int removed = layer.size();
    while (removed < n) {
        vector<int> next;
        for (int u : layer)
            for (int v : adj[u])
                if (--deg[v] == 1) next.push_back(v);
        removed += next.size();
        layer = next;
    }
    return layer;               // 1 or 2 centers
}

Each vertex is added to a layer once and each edge decremented once, so the whole thing is linear.

Method 2: midpoint of the diameter — $O(n)$

Find the diameter path with two BFS runs, then walk to its middle. With diameter length $d$ (in edges), the center is the vertex at distance $\lfloor d/2\rfloor$ from either endpoint; when $d$ is odd, both middle vertices are centers.

Center vs centroid — do not confuse them

	Center	Centroid
Minimises	maximum distance (eccentricity)	maximum subtree size
Count	1 or 2	1 or 2
Found by	leaf peeling / diameter midpoint	one DFS on subtree sizes
Used for	canonical rooting, minimising height, isomorphism	centroid decomposition
Guarantee	eccentricity = radius	every component after removal has $\le n/2$ vertices

They can be different vertices. A star with a long tail has its centroid at the hub but its center out along the tail.

Why the center is the canonical root

An unrooted tree has no natural root, so comparing two unrooted trees requires a canonical choice. The center is that choice: it is defined purely by the tree’s structure, so isomorphic trees have corresponding centers. Since there are at most two, AHU isomorphism testing roots one tree at its center and tries both centers of the other — at most two comparisons.

Uses

• Minimum-height rooting — the height when rooted at a center equals the radius $\lceil d/2\rceil$.
• Facility location on a tree — placing one facility to minimise the worst-case distance means placing it at the center (or at the midpoint of the diameter edge, if fractional positions are allowed).
• Tree isomorphism and hashing — canonical rooting.
• Merging two trees to minimise the resulting diameter — join their centers.

See also: Tree Diameter · Tree Isomorphism · Centroid Decomposition