Tree Centers and Centroids

A center and a centroid solve different balancing problems. A center minimizes the maximum distance to any vertex. A centroid balances vertex counts: after removing it, every remaining connected component contains at most half the original vertices. These definitions can select different vertices of the same tree.

Centers are useful when minimizing the worst travel distance or choosing a shallowest possible root. Centroids support balanced divide-and-conquer and counting algorithms. This lesson computes both in linear time, compares their guarantees, and avoids treating two similarly named concepts as interchangeable.

Prerequisites: Subtree Sizes; Tree Diameter. All distances in this lesson are unweighted edge counts.

Build the idea

1. 1. Center: balance distance

   The eccentricity of v is the largest distance from v to any vertex. A center minimizes eccentricity; the minimum value is called the radius. If a diameter has length D, every vertex is at distance at least ceil(D/2) from one of its endpoints. The middle vertex or two middle vertices of a diameter achieve that bound in an unweighted tree. Consequently radius=ceil(D/2), and a tree has one center when D is even or two adjacent centers when D is odd.

   An equivalent algorithm repeatedly removes all current degree-1 leaves simultaneously until at most two vertices remain. Removing an outer layer shortens longest routes from both ends while preserving their middle. This is why layer removal finds centers rather than arbitrary vertices left by a sequential deletion order.

2. 2. Peel complete layers safely

   Initialize degree[v] to the adjacency-list length. Queue every vertex of degree at most 1, including the single-vertex case. While more than two vertices remain, remove exactly the queue size recorded at the start of that round. Decrease each surviving neighbor degree and enqueue it when the degree becomes 1. Leaves discovered during this round belong to the next round, so do not remove them immediately.

   For path 1–2–3–4–5, first remove {1,5}, leaving {2,3,4}; then remove {2,4}, leaving center {3}. On path 1–2–3–4, one round leaves centers {2,3}. A star leaves only its hub.

3. 3. Centroid: balance component sizes

   Root the tree anywhere and compute parent[] and subtree[]. Removing v leaves one component for each child, of size subtree[child], and an optional parent-side component of size N−subtree[v]. Let largest[v] be the maximum of these values. Vertex v is a centroid exactly when largest[v]≤floor(N/2). The root needs no separate formula: its parent-side size is zero.

   Why does a centroid exist? Start anywhere. If removing the current vertex leaves a component larger than N/2, move into that component. There can be only one such component. After moving, the component behind you has fewer than N/2 vertices, so you never need to step back; continuing must end at a centroid. There are at most two centroids, and if there are two they are adjacent. The code simply checks every vertex after one subtree pass.

4. 4. See the definitions disagree

   Use path 1–2–3–4–5 and add leaves 6,7,8 to vertex 1. There are eight vertices. A diameter from 6 to 5 has length 5, so the centers are 2 and 3. Removing vertex 1 leaves a component {2,3,4,5} of size 4 and three singleton components. Thus 1 is a centroid. Removing 2 leaves {1,6,7,8} and {3,4,5}, of sizes 4 and 3, so 2 is also a centroid. The center set {2,3} and centroid set {1,2} are different.

5. 5. Choose the right tool

   For a facility minimizing its farthest unweighted client distance, use a center. For recursively splitting a tree so no recursive component exceeds half its previous size, use a centroid. Picking a center does not guarantee balanced component sizes, and picking a centroid does not guarantee minimum eccentricity. Weighted variants require precise definitions: edge weights affect distance centers; vertex weights affect weighted centroid balance.

   The implementation prints both sets in increasing vertex order for deterministic samples. It uses independent degree and subtree arrays, because center peeling must not destroy the original adjacency lists needed by the centroid computation.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
void print(vector<int>vertices){
    sort(vertices.begin(),vertices.end());
    for(int i=0;i<(int)vertices.size();++i){
        cout<<vertices[i]<<(i+1==(int)vertices.size()?'\n':' ');
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int>degree(n+1);
    queue<int>leaves;
    for(int v=1;v<=n;++v){
        degree[v]=(int)graph[v].size();
        if(degree[v]<=1){
            leaves.push(v);
        }
    }
    // Stop with one or two centers, removing a complete outer layer each round.
    int remaining=n;
    while(remaining>2){
        int layer=(int)leaves.size(); // Only this round's leaves.
        remaining-=layer;
        while(layer--){
            int v=leaves.front();
            leaves.pop();
            for(int next:graph[v]){
                if(--degree[next]==1){
                    leaves.push(next);
                }
            }
        }
    }
    vector<int>centers;
    while(!leaves.empty()){
        centers.push_back(leaves.front());
        leaves.pop();
    }
    // Root the original unchanged tree to compute child component sizes.
    vector<int>parent(n+1),order,subtree(n+1,1);
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        order.push_back(v);
        for(int next:graph[v]){
            if(next!=parent[v]){
                parent[next]=v;
                q.push(next);
            }
        }
    }
    // Reversed traversal finishes children before their parents.
    for(int i=n-1;i>0;--i){
        int v=order[i];
        subtree[parent[v]]+=subtree[v];
    }
    vector<int>centroids;
    for(int v=1;v<=n;++v){
        int largest=n-subtree[v]; // Component toward the parent.
        for(int next:graph[v]){
            if(parent[next]==v){
                largest=max(largest,subtree[next]);
            }
        }
        // A centroid leaves no component containing more than half the vertices.
        if(largest<=n/2){
            centroids.push_back(v);
        }
    }
    print(centers);
    print(centroids);
}

Complexity analysis

O(N) time for leaf peeling, rooting, subtree accumulation, and centroid checks. Every original edge is examined only a constant number of times. O(N) memory. Sorting the final sets is O(1), since each set has at most two vertices.

Example input and output

N, followed by N−1 edges of a valid unweighted tree. First print center(s), then centroid(s), each in increasing order.

Input

8
1 2
2 3
3 4
4 5
1 6
1 7
1 8

Output

2 3
1 2

A length-5 diameter has middle vertices 2 and 3. Removing 1 or 2 leaves no component larger than four vertices, so those are the centroids.

Practical applications

Centers minimize maximum unweighted distance and give minimum tree height over root choices. Centroids enable logarithmic-depth centroid decomposition. Tree isomorphism can root at centers; balanced divide-and-conquer typically roots at centroids.

Check your understanding

Which condition identifies a centroid?

Put it into practice

Also print the radius and the largest remaining component size for every centroid.