Computing and Comparing Tree Centers and Centroids

Two Different Ways to Balance a Tree

A tree can be balanced in more than one sense. Its center consists of the vertex or vertices with the smallest possible maximum distance to all other vertices. Its centroid consists of the vertex or vertices whose deletion leaves components as small as possible in the sense that no component contains more than half the tree’s vertices. The center concerns distances; the centroid concerns component sizes. These are different measurements, so their answers need not be the same.

All graphs in this tutorial are finite, simple, undirected trees. For vertices \(u,v\), distance \(d(u,v)\) is the number of edges in a shortest path. The eccentricity of \(v\) is \(\operatorname{ecc}(v)=\max_{u\in V}d(u,v)\). The radius is the minimum eccentricity, and a center is a vertex attaining that minimum. A diameter is a path of maximum length, and its length is the diameter of the tree. A centroid is a vertex \(v\) such that every component of \(T-v\) has at most \(|V|/2\) vertices.

Deleting a vertex of a tree separates it into one component for each neighbor of that vertex. To test whether a vertex is a centroid, count the vertices in every such component and compare the largest count with \(n/2\). To find a center, first find a diameter path; its middle vertex, or the two vertices at the ends of its middle edge, give the center.

Why the Middle of a Diameter Gives the Center

Proof. Write the diameter path as \(p_0,p_1,\ldots,p_D\), so its endpoints are \(p_0\) and \(p_D\). For a vertex \(p_i\) on the path, its distances to these endpoints are \(i\) and \(D-i\). Therefore \(\operatorname{ecc}(p_i)\geq \max(i,D-i)\).

We show that this lower bound is also an upper bound. Take any vertex \(z\) of the tree. The unique path from \(z\) to \(P\) first meets \(P\) at some \(p_j\); let \(h=d(z,p_j)\). Since \(p_0,\ldots,p_D\) is a diameter path, the paths from \(z\) to either endpoint cannot have length greater than \(D\). Thus \(h+j\leq D\) and \(h+D-j\leq D\), so \(h\leq \min(j,D-j)\). The path from \(p_i\) to \(z\) has length \(|i-j|+h\). If \(j\leq i\), then this is at most \(i-j+j=i\). If \(j\geq i\), it is at most \(j-i+D-j=D-i\). In either case it is at most \(\max(i,D-i)\). This holds for every \(z\), so \(\operatorname{ecc}(p_i)=\max(i,D-i)\).

Now let \(z\) be off \(P\), and let \(p_j\) be where its path first meets \(P\). Put \(h=d(z,p_j)\), so \(h\geq1\). Its distances to \(p_0\) and \(p_D\) are \(h+j\) and \(h+D-j\); hence \(\operatorname{ecc}(z)\geq h+\max(j,D-j)\). This is strictly greater than \(\max(j,D-j)\), which is at least the minimum of \(\max(i,D-i)\) over \(0\leq i\leq D\). So no vertex off \(P\) is a center. On \(P\), the quantity \(\max(i,D-i)\) is minimized at the middle index if \(D\) is even, and at the two middle indices if \(D\) is odd. Those are therefore exactly the centers. \(\square\)

This result gives a direct procedure: choose a diameter path and count in from both ends. It also verifies the result without computing every vertex’s eccentricity. The proof explains why branches off the diameter cannot produce a better center: their vertices are farther from both diameter endpoints than their attachment points are.

Computing Centroids from Component Sizes

The centroid test uses the actual sizes of the components, not how far they extend. In a tree, those sizes can be computed efficiently by rooting the tree at any vertex. The subtree of a vertex \(v\) consists of \(v\) and all its descendants in the chosen rooting; write its size as \(s(v)\). After deleting \(v\), each child \(w\) of \(v\) contributes a component of size \(s(w)\). If \(v\) has a parent, the component in the parent’s direction has size \(n-s(v)\). These counts cover all components of \(T-v\).

Proof. Removing \(v\) separates the tree into the components reached through its neighbors. For each child \(w\), its descendants and \(w\) itself form exactly the component reached through \(w\), of size \(s(w)\). If \(v\) has a parent, all vertices outside \(v\)’s subtree lie in the component reached through the parent, of size \(n-s(v)\). There are no other components because every neighbor is either the parent or a child. The definition of centroid requires every one of these component sizes to be at most \(n/2\), which is precisely the stated test. If the root is \(v\), there is no parent component, so only the child conditions apply. \(\square\)

Each vertex needs only its child-subtree sizes and, except at the root, the size on its parent side. Once the subtree sizes have been counted, the centroid test does not require a fresh search of the entire tree for each candidate vertex.

A Tree Whose Center and Centroid Differ

When Both Sets Have Two Vertices

Proof. For any edge \(uv\), deleting the edge separates the tree into two sides. If \(u\) is a centroid, the side containing \(v\) has size at most \(n/2\), since it is one of the components of \(T-u\). If \(v\) is also a centroid, the side containing \(u\) has size at most \(n/2\). The two side sizes sum to \(n\), so both must equal \(n/2\). In particular, \(n\) is even.

Now suppose two distinct centroids \(u,v\) were not adjacent, and consider the first edge \(ux\) on the path from \(u\) to \(v\). The side of this edge containing \(x\) has size at most \(n/2\), because it is a component of \(T-u\). Since \(v\) is not \(x\), deleting \(v\) leaves a component containing \(u\) that includes all vertices on the \(u\)-side of the edge \(ux\) and also \(x\). If the \(x\)-side has size less than \(n/2\), the \(u\)-side already has more than \(n/2\) vertices, contradicting that \(v\) is a centroid. If the \(x\)-side has size \(n/2\), the \(u\)-side has size \(n/2\), and the component containing \(u\) after deleting \(v\) includes \(x\) as well, so has more than \(n/2\) vertices, again a contradiction. Thus distinct centroids must be adjacent. Since a tree has no three pairwise adjacent vertices, it cannot have three centroids. \(\square\)

Common Pitfall: Mixing Up the Tests

A frequent error is to use the diameter midpoint rule to identify a centroid, or the component-size rule to identify a center. In the long-arm example, \(x\) is the centroid because the largest component after deleting it has size \(4\), no more than \(9/2\). But \(x\) is not a center: its distance to \(a_4\) is \(4\), whereas the centers \(a_1,a_2\) have eccentricity \(3\). Conversely, the diameter rule identifies \(a_1,a_2\) as centers, but deleting either leaves a component larger than \(9/2\), so neither is a centroid.

When computing, write down the quantity being tested. For a center, compare maximum distances to all vertices. For a centroid, list every component size after deletion and compare each with \(n/2\), including the strict failure case of a size greater than \(n/2\). Neither definition asks for the same kind of balance: one limits travel distance, the other limits how many vertices lie in a component.