Fast approximation of search trees on trees with centroid trees

Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a path. An optimal BST of size $n$ can be computed for a given distribution of queries in $O(n^2)$ time [Knuth 1971] and centroid BSTs provide a nearly-optimal alternative, computable in $O(n)$ time [Mehlhorn 1977]. By contrast, optimal STTs are not known to be computable in polynomial time, and the fastest constant-approximation algorithm runs in $O(n^3)$ time [Berendsohn, Kozma 2022]. Centroid trees can be defined for STTs analogously to BSTs, and they have been used in a wide range of algorithmic applications. In the unweighted case (i.e., for a uniform distribution of queries), a centroid tree can be computed in $O(n)$ time [Brodal et al. 2001; Della Giustina et al. 2019]. These algorithms, however, do not readily extend to the weighted case. Moreover, no approximation guarantees were previously known for centroid trees in either the unweighted or weighted cases. In this paper we revisit centroid trees in a general, weighted setting, and we settle both the algorithmic complexity of constructing them, and the quality of their approximation. For constructing a weighted centroid tree, we give an output-sensitive $O(n\log h)\subseteq O(n\log n)$ time algorithm, where $h$ is the height of the resulting centroid tree. If the weights are of polynomial complexity, the running time is $O(n\log\log n)$. We show these bounds to be optimal, in a general decision tree model of computation. For approximation, we prove that the cost of a centroid tree is at most twice the optimum, and this guarantee is best possible, both in the weighted and unweighted cases. We also give tight, fine-grained bounds on the approximation-ratio for bounded-degree trees and on the approximation-ratio of more general $\alpha$-centroid trees.


Introduction
Search trees on trees (STTs) are a far-reaching generalization of binary search trees (BSTs), modeling the exploration of tree-shaped search spaces. Given an undirected tree T , an STT on T is a tree rooted at an arbitrary vertex r of T , with subtrees built recursively on the components resulting after removing r from T , see Figure 1 for an example. BSTs correspond to the special case where the underlying tree T is a path.
STTs and, more generally, search trees on graphs arise in several different contexts and have been studied under different names: tubings [CD06], vertex rankings [DKKM94, BDJ + 98, ES14], ordered colorings [KMS95], elimination trees [Liu90,PSL90,AH94,BGHK95]. STTs have been crucial in many algorithmic applications, e.g., in pattern matching and counting [Fer13, KPR + 14, GHLW15], cache-oblivious data structures [BFCK06,FV16], tree clustering [FJ83], geometric visibility [GHL + 87], planar point location [GT98], distance oracles [CGMW21]. They arise in matrix factorization (e.g., see [DER17,§ 12]), and have also been related to the competitive ratio in certain online hitting set problems [ES14]. Similarly to the setting of BSTs, a natural goal is to find an STT in which the expected depth of a vertex is as small as possible; we refer to such a tree as an optimal tree, noting that it is not necessarily unique. This optimization task can be studied both for the uniform probability distribution over the vertices, and for the more general case of an arbitrary distribution given as input. We refer to the first as the unweighted and the second as the weighted problem.
For BSTs, both the unweighted and the weighted problems are well-understood. In the unweighted case, a simple balanced binary tree achieves the optimum. In the weighted case, an optimal tree on n vertices can be found in time O(n 2 ) by Knuth's algorithm [Knu71], a textbook example of dynamic programming. No faster algorithm is known in general, although Larmore's algorithm [Lar87] achieves better bounds under certain regularity assumptions on the weights; for example, if the probability assigned to each vertex is Ω(1/n), then the optimum can be found in time O(n 1.591 ).
By contrast, the complexity of computing an optimal STT is far less understood. Even in the unweighted case, no polynomial-time algorithm is known, and the problem is not known to be NP-hard even with arbitrary weights. Recently, a PTAS was given for the weighted problem [BK22], but its running time for obtaining a (1 + ε)-approximation of the optimal STT is O(n 1+2/ε ), which is prohibitive for reasonably small values of ε. Note that the apparently easier problem of minimizing the maximum depth of a vertex, i.e., computing the treedepth of a tree, can be solved in linear time by Schäffer's algorithm [Sch89], and treedepth itself has many algorithmic applications, e.g., see [NdM12,§ 6,7].
Centroid trees. Given the relatively high cost of computing optimal binary search trees, research has turned already half a century ago to efficient approximations. Mehlhorn has shown [Meh75,Meh77] that a simple BST that can be computed in O(n) time closely approximates the optimum. More precisely, both the optimum cost and the cost of the obtained tree are in [H/log(3), H + 1], where H is the binary entropy of the input distribution. 1 Alternatively, the cost can be upper bounded by OPT + log (OPT) + log e, where OPT is the cost of the optimal tree. Observe that this means that the approximation ratio gets arbitrarily close to 1 as OPT goes to infinity. 2 The BST that achieves the above guarantees is built by recursively picking roots such as to make the weights of the left and right subtrees "as equal as possible". This is a special case of a centroid tree, defined as follows. Given a tree T , a centroid of T is a vertex whose removal from T results in components with weight at most half of the total weight of T . A centroid tree is built by iteratively finding a centroid and recursing on the components resulting after its removal. See Figure 1 for an example.
The fact that an (unweighted) centroid always exists was already shown in the 19-th century by C. Jordan [Jor69]. We sketch the easy, constructive argument that also shows the existence of a weighted centroid: start at an arbitrary vertex of T and, as long as the current vertex is not a centroid, move one edge in the direction of the component with largest weight. It is not hard to see that the procedure succeeds, visiting each vertex at most once.
A straightforward implementation of the above procedure finds an unweighted centroid tree in O(n log n) time. This running time has been improved to O(n) by carefully using data structures [BFPÖ01,GPV19]. The run-time guarantees however, do not readily generalize from the unweighted to the weighted setting. Intuitively, the difficulty lies in the fact that in the weighted case, the removal of a centroid vertex may split the tree in a very unbalanced way, leaving up to n − 1 vertices in one component. Thus, a naive recursive approach will take Θ(n 2 ) time in the worst case.
Most algorithmic applications of STTs, including those mentioned before, rely on centroid trees. It is therefore surprising that nothing appears to be known about how well the centroid tree approximates the optimal STT in either the unweighted or weighted cases. In this paper we prove that the centroid tree is a 2-approximation of the optimal STT, and that the factor 2 is, in general, best possible, both in the unweighted and weighted settings. As our main result, we also show a more precise bound on the approximation ratio of centroid trees, in terms of the maximum degree of the underlying tree T . 3 Before stating our results, we need a few definitions. Consider an undirected, unrooted tree T given as input, together with a weight function w : V (T ) → R ≥0 . For convenience, for any subgraph H of T , we denote w(H) = x∈V (H) w(x). (To interpret the weights as probabilities, we need the condition w(T ) = 1. It is, however, often convenient to relax this requirement and allow arbitrary non-negative weights, which is the approach we take in this paper.) A search tree on T is a rooted tree T with vertex set V (T ) whose root is an arbitrary vertex r ∈ V (T ). The children of r in T are the roots of search trees built on the connected components of the forest T − r. A tree consisting of a single vertex admits only itself as a search tree. (See Figure 1.) It follows from the definition that for all x, the subtree T x of T rooted at x induces a connected subgraph T [V (T x )] of T , and moreover, T x is a search tree on T [V (T x )].
The cost of a search tree T on T is cost w (T ) = x∈V (T ) w(x) · depth T (x), where the depth of the root is taken to be 1. The optimum cost OPT(T , w) is the minimum of cost w (T ) over all search trees T of T .
for all x ∈ V (T ). In general, the centroid tree is not unique, and centroid trees of the same tree can have different costs. 4 We denote by cent(T , w) the maximum cost of a centroid tree of (T , w), with weight function w.
We can now state our approximation guarantee for centroid trees.
Theorem 1.1. Let T be a tree, w : V (T ) → R ≥0 , and m = w(T ). Then We show that this result is optimal, including in the additive term. Moreover, the constant factor 2 cannot be improved even for unweighted instances.
Theorem 1.2. (i) For every ε > 0 there is a sequence of instances (T n , w n ) with w n (T n ) = 1, and for every centroid tree C n of (T n , w n ) 3 In their recent paper on dynamic STTs, Bose, Cardinal, Iacono, Koumoutsos, and Langerman [BCI + 20] remark that the ratio between the costs of the centroid-and optimal trees may be unbounded. In light of our results, this observation is erroneous. It is true, however, that a centroid tree built using the uniform distribution may be far from the optimum w.r.t. a different distribution. 4 Consider, for instance the two different centroid trees of a path on four vertices, with weights (0.2, 0.3, 0.2, 0.3).
(ii) There is a sequence of instances (T n , w n ), where w n is the uniform distribution on V (T n ), and for every centroid tree C n of (T n , w n ) lim n→∞ cost wn (C n ) OPT(T n , w n ) = 2.
In both cases lim n→∞ OPT(T n , w n ) = ∞.
Note that the fact that lim n→∞ OPT(T n , w n ) = ∞ in Theorem 1.2 establishes that the asymptotic approximation ratio is 2. By this we mean that every bound of the form cent ≤ c · OPT + o(OPT) must have c ≥ 2.
We next show a stronger guarantee when the underlying tree has bounded degree.
Theorem 1.3. Let T be a tree, w : V (T ) → R ≥0 , and let ∆ be the maximum degree of T . Then We complement this result by two lower bounds. The first establishes the tightness of the approximation ratio. The second shows a (slightly smaller) lower bound on the approximation ratio for instances where OPT is unbounded.
(i) There is a sequence of instances (T n , w n ) such that T n has maximum degree at most ∆, and for every centroid tree C n of (T n , w n ) (ii) There is a sequence of instances (T n , w n ) such that T n has maximum degree at most ∆, lim n→∞ OPT(T n , w n ) = ∞, w n (T n ) = 1, and for every centroid tree C n of (T n , w n ) We remark that Theorem 1.4(i) does not exclude the possiblity of a bound of the form cent ≤ c·OPT+o(OPT), where c < 2 − 1 2 ∆ , as here OPT(T n , w n ) is bounded. Part (ii), however, establishes that a bound of the form We leave open the problem of closing the gap in the asymptotic approximation ratio in terms of ∆.
Computing centroid trees. On the algorithmic side, we show that the weighted centroid tree can be computed in O(n log n) time. Previously, the fastest known constant-approximation algorithm [BK22] took O(n 3 ) time (similarly achieving an approximation ratio of 2). The main step of our algorithm, finding the weighted centroid of a tree, is achievable in O(log n) time, assuming that the underlying tree is stored in a top tree data structure [AHLT05]. Iterating this procedure in combination with known algorithms for constructing and splitting top trees yields the algorithm that runs in O(n log n) time. We also develop an improved, output-sensitive algorithm, with running time O(n log h), where h is the height of the resulting centroid tree, yielding a running time O(n log log n) in the typical case when the height is O(log n).
Theorem 1.5. Let T be a tree on n vertices and w be a weight function. We can compute a centroid tree of (T , w) in time O(n log h), where h is the height of the computed centroid tree.
One may ask whether the weighted centroid tree can be computed in linear time, similarly to the unweighted centroid tree, or to the weighted centroid BST. We show that, assuming a general decision tree model of computation, this is not possible, and the algorithm of Theorem 1.5 is optimal for all n and h (up to a constant factor). Our lower bound on the running time applies, informally, to any deterministic algorithm in which the input weights affect program flow only in the form of binary decisions, involving arbitrary computable functions. The model thus excludes using the weights for addressing memory, e.g., via hashing.
More precisely, consider a tree T on n vertices. We say that a binary decision tree D T solves T for a class of weight functions W mapping V (T ) to R ≥0 , if the leaves of D T are search trees on T , every branching of D T is of the form "f (w)≥0?" for some computable function f : W → {−1, +1}, and for every weight function w ∈ W, starting from the root of D T and following branchings down the tree, we reach a leaf T of D T that is a valid centroid tree for (T , w). The height of D T is then a lower bound on the worst-case running time.
Theorem 1.6. Let h ≥ 3 and n ≥ h + 1 be integers. Then there is a tree T on at most n vertices and a class W of weight functions on V (T ) such that for every w ∈ W, every centroid tree of (T , w) has height h, and every binary decision tree that solves T for W has height Ω(n log h).
We can nonetheless improve the running time, when the weights are restricted in certain (natural) ways. We define the spread σ of a weight function w as the ratio between the total weight w(T ), and the smallest non-zero weight of a vertex. As we show, O(n log h) ⊆ O(n log log (σ + n)) and therefore, when σ ∈ n O(1) (for instance, if the weights are integers stored in RAM words), we obtain a running time of O(n log log n).
When many vertices have zero weight, we obtain further improvements, e.g., if only O(n/ log n) of the weights are non-zero, we can compute a centroid tree in O(n) time, even if the height h is large. We defer the precise statement of these refined bounds and the discussion of their optimality to Section 5.
Approximate centroid trees. Finally, we consider the approximation guarantees of a generalized form of centroid trees. Let us call a vertex v of a tree T an α-centroid, Observe that the standard centroid tree is a 1 2 -centroid tree, and all STTs are 1-centroid trees. Also note that an α-centroid is a β-centroid for all β ≥ α and that the existence of an α-centroid is not guaranteed for α < 1 2 (consider a single edge with the two endpoints having the same weight). On the other hand, an α-centroid for α < 1 2 , if it exists, is unique, and therefore the α-centroid tree is also unique. To see this, consider an α-centroid c that splits T into components T 1 , . . . , T k . If an alternative α-centroid c were in component T i , then its removal would yield a component containing all vertices in T − V (T i ), of weight at least (1 − α) · w(T ) > α · w(T ).
Denote by cent α (T , w) the maximum cost of an α-centroid tree of (T , w), or 0 if no α-centroid tree exists. We refine our guarantee from Theorem 1.1 to approximate centroid trees: Note that the second bound is a strengthening of the first when α < 1 2 . In particular, for α ≤ 1 3 , it implies that an α-centroid tree is optimal, if it exists.
We show that the result is tight when α ≥ 1 2 by proving a matching lower bound. Theorem 1.8. For every α ∈ [ 1 2 , 1) there is a sequence of instances (T n , w n ) with lim n→∞ OPT(T n , w n ) = ∞, w n (T n ) = 1 and Note that if α > 1 2 , we cannot prove such a lower bound for all α-centroid trees of (T n , w n ) (as in Theorem 1.2), since a 1 2 -centroid tree exists and has stronger approximation guarantees according to Theorem 1.1.
Finally, we argue that every optimal STT is a 2 3 -centroid tree. A special case of this result (for BSTs) was shown by Hirschberg, Larmore, and Molodowitch [HLM86], who also showed that the ratio 2 3 is tight (in the special case of BSTs, and thus, also for STTs).
Theorem 1.9. Let T be an optimal STT of (T , w). Then, T is a 2 3 -centroid tree of (T , w).
Structure of the paper. In Section 2 we state a number of technical results needed in the proofs.
In Section 3 we prove the general upper and lower bounds on the approximation ratio of centroid trees (Theorems 1.1 and 1.2). In Section 4 we prove the fine-grained bounds on the approximation ratio of centroid trees (Theorems 1.3 and 1.4). Section 5 contains the algorithmic results (Theorem 1.5 and extensions) and the lower bounds (Theorems 1.6 and extensions). Results on α-centroids (Theorems 1.7, 1.8, and 1.9) are proved in Section 6. In Section 7 we conclude with open questions.
Related work. Different models of searching in trees have also been considered, e.g., the one where we query edges instead of vertices [BFN99,LN01,MOW08,OP06], with connections to searching in posets [LS85,HIT11]. In the edge-query setting, Cicalese, Jacobs, Laber and Molinaro [CJLM11,CJLM14] study the problem of minimizing the average search time of a vertex, and show this to be an NP-hard problem [CJLM11]. They also show that an "edge-centroid" tree (in their terminology, a greedy algorithm) gives a 1.62-approximation of the optimum [CJLM14]. STTs generalize BSTs, therefore it is natural to ask to what extent the theory developed for BSTs can be extended to STTs. Defining a natural rotation operation on STTs, Bose, Cardinal, Iacono, Koumoutsos, and Langerman [BCI + 20] develop an O(log log n) competitive dynamic STT, analogously to Tango BSTs [DHIP07]. In a similar spirit, Berendsohn and Kozma [BK22] generalize Splay trees [ST85] to STTs. The rotation operation on STTs naturally leads to the definition of tree associahedra, a combinatorial structure that extends the classical associahedron defined over BSTs or other Catalan-structures. Properties of tree-and more general graph associahedra have been studied in [CD06,Dev09,CMPP15,CLP18,CPV21,Ber22].

Preliminaries
Given a graph G, we denote by V (G) its set of vertices, by E(G) its set of edges, and by C(G) its set of connected components. If v ∈ V (G), denote by N G (v) the set of neighbors of v in G, and deg G (v) = |N G (v)|. For S ⊆ V (G), denote by G[S] the subgraph of G induced by S, and for brevity, The following observation is straightforward.
Observation 2.1. Let T be a search tree on T , w : V (T ) → R ≥0 , m = w(T ) and r = root(T ). For each component H ∈ C(T − r), denote by T H the subtree of T rooted at the unique child of r in H. Then Given a search tree T on a tree T and a subgraph H of T , we denote by LCA T (H) the vertex with maximal depth in T that is an ancestor of all vertices of H.
The following two technical lemmas will be useful later.  Proof. Let c 1 ∈ A and c 2 ∈ B be centroids. If , we are done. Otherwise, there must be a vertex c on the path between c 1 and c 2 such that c ∈ V (A) ∩ V (B). We show that c is a centroid. Let . This concludes the proof.
Projection of a search tree. For a rooted tree T and a vertex v ∈ V (T ), we denote by Path T (v) the set of vertices on the path in T from root(T ) to v, including both endpoints. The proofs of our upper bounds require the following notion of projection of a search tree.
Theorem 2.1. Let T be a search tree on T and H a connected subgraph of T . There is a unique search tree T | H on H such that for every v ∈ V (H), Definition 2.1 (Projection). Let T be a search tree on T and H a connected subgraph of T . We call T | H , whose existence is established by Theorem 2.1, the projection of T to H.
An equivalent notion of projection was used by Cardinal, Langerman and Perez-Lantero [CLP18] without explicitly stating Theorem 2.1, and a closely related notion was used by Cicalese, Jacobs, Laber and Molinaro [CJLM14] in the edge-query setting. In Appendix A we prove Theorem 2.1, present the definition of a projection used by Cardinal et al. and show that the two definitions are equivalent.
Median and centroid. A certain concept of a median vertex of a tree has been used previously in the literature. If T is a tree with positive vertex weights and positive edge weights, then the median of T is the vertex v minimizing the quantity u =v w(u) · d(u, v). Here w(u) is the weight of the vertex u, and d(u, v) is the distance from u to v, i.e., the sum of the edge weights on the path from u to v. We show (proof in Appendix B) that if all edge-weights are 1, then medians are precisely centroids.
Lemma 2.3. Let T be a graph and w be a weight function on V (T ).
Breaking ties. Our lower bounds require the following tie-breaking procedure, with proof in Appendix C.
Lemma 2.4. Let T be a tree, w : V (T ) → R ≥0 a weight function and let C be a centroid tree of (T , w). For every ε > 0 there exists a weight function w : V (T ) → R ≥0 such that C is the unique centroid tree of (T , w ) and w − w ∞ < ε.
Contractions in weighted trees. Let T be a tree, let w : V (T ) → R ≥0 be a weight function, and let {u, v} be an edge of T . Then contracting {u, v} produces a tree T and a weight function w , defined as follows. The tree T is obtained from T by removing u and v, adding a new vertex s, and setting The lemma below shows that contractions essentially preserve centroids.
Lemma 2.5. Let T be a tree and w : V (T ) → R ≥0 be a weight function, and let T , w be obtained from T , w by contracting the edge {u, v} into a new vertex s. Then s is a centroid of (T , w ) if and only if u or v is a centroid of (T , w); and x is a centroid of (T , w ) if and only if x is a centroid of (T , w), for each Proof. W.l.o.g., assume that w(T ) = 1. Consider first a vertex x ∈ V (T ) − {u, v}. The contraction {u, v} does not change the weight of any component H ∈ C(T − x). Thus, x is a centroid of (T , w) if and only if it is a centroid of (T , w ). Consider now the vertices u, v, and s. Observe that C(T − {u, v}) = C(T − s), and the contraction does not affect the weights of these components. If u or v is a centroid of (T , w), then no component of C(T − {u, v}) has weight more than 1 2 . Thus, s is a centroid of (T , w ). On the other hand, suppose that s is a centroid of (T , w ). Consider a component Thus, either u or v is a centroid of (T , w ).

Approximation guarantees for general trees
In this section we prove the general upper and lower bounds on the approximation quality of centroid trees.

Upper bound
We start with a lemma.
Lemma 3.1. Let c be a centroid of (T , w) and m = w(T ). Then OPT(H, w). (1) Proof. Let T be an arbitrary search tree on T . We will show that cost w (T ) is at least the right hand side of Equation (1). Denote r = root(T ). If r = c, using Observation 2.1, we have which implies the claim. Assume therefore that r = c. Denote by H * the connected component of Summing the contributions of all the vertices, we get where the last inequality follows from c being a centroid.
Proof of Theorem 1.1. The proof is by induction on the number of vertices. When |V (T )| = 1 we have as required.
Assume |V (T )| > 1. Let C be a centroid tree on T and c = root(C). Using Observation 2.1 and the induction hypothesis we have which is just a re-arrangement of Lemma 3.1. This concludes the proof.
We note that in the edge-query model of search trees a 2-approximation was shown in [CJLM14] using similar techniques. In contrast to that result, however, our approximation guarantee is best possible.

Lower bounds
In the following, we show the tightness of Theorem 1.1 through the following lower bounds.
Theorem 1.2. (i) For every ε > 0 there is a sequence of instances (T n , w n ) with w n (T n ) = 1, and for every centroid tree C n of (T n , w n ) (ii) There is a sequence of instances (T n , w n ), where w n is the uniform distribution on V (T n ), and for every centroid tree C n of (T n , w n ) lim n→∞ cost wn (C n ) OPT(T n , w n ) = 2.
In both cases lim n→∞ OPT(T n , w n ) = ∞.
Part (i). We proceed by constructing a sequence (T n , w n ) such that for some centroid tree C n , Using Lemma 2.4, we can then add an arbitrarily small perturbation to w n to make C n the unique centroid tree. (Observe that for every search tree T , cost w (T ) is continuous in w, therefore so is OPT(T , w).) The sequence (T n , w n ) is constructed recursively as follows. For the sake of the construction we view T n as a rooted tree. The base case T 0 is a tree with a single vertex v and w 0 (v) = 1. For n > 0, take two copies (A, w A ) and (B, w B ) of (T n−1 , w n−1 ). Connect the roots of A and B to a new vertex c. Finally, set root(T n ) = root(A) (see Figure 2). We define w n as follows. (observe that w n (T n ) = 1, by induction on n.) Let C n denote the search tree on T n obtained by setting c as the root and recursing. Observe that C n is a centroid tree of (T n , w n ).
Lemma 3.2. The following hold (a) cost wn (C n ) = n + 1, Proof. Let c n = cost wn (C n ). Clearly, c 0 = 1. Assume n > 0. Let C A and C B be search trees on A and B respectively, each a copy of C n−1 . By construction of C n we have and (a) follows by induction. Using (a) and Theorem 1.1, part (b) follows: Next, in order to bound OPT(T n , w n ) from above, we construct a sequence of search trees T n on T n . For n = 0, tree T 0 is a single vertex. Assume n > 0. Let A, B, and c be as in the definition of T n . Let T A and T B be search trees over A and B respectively, each a copy of T n−1 . Denote r A = root(A) and r B = root(B). Tree T n is obtained by adding an edge from r A to r B and an edge from r B to c, and setting root(T n ) = r A . Lemma 3.3. cost wn (T n ) = n 2 + 1. Proof. Denote t n = cost wn (T n ). Clearly t 0 = 1. Assume n > 0. The contribution of vertices of A to t n is exactly 1 2 cost w A (T A ) = tn−1 2 . Since r is an ancestor of all vertices in B, the contribution of these vertices to t n is exactly 1 . Summing the contribution of all vertices, we get t n = t n−1 + 1 2 and the claim follows.
Part (ii). Let T n , C n and T n be as in the proof of Theorem 1.2(i). Let µ n : V (T n ) → R ≥0 be the constant function µ n (v) = 1. Let A, B and c be as in the construction of T n . Observe that c is the unique centroid of (T n , µ n ). By induction, C n is the unique centroid tree of (T n , µ n ).
Observe that t n = 2 n n + 2 n+1 − 1 is the solution to this formula.
Proof of Theorem 1.2(ii). Denote byμ n the uniform distribution over V (T ). Using Lemma 3.4 we have We also have therefore, using Theorem 1.1, also OPT(T n ,μ n ) → ∞. This concludes the proof.

Approximation guarantees for trees with bounded degrees
In this section we show the upper and lower bounds on the approximation quality of centroid trees when the underlying tree T has bounded degree. Proof of Theorem 1.3. The proof is by induction on |V (T )|. Let T be any search tree on T . We will show that cent(T ) ≤ 2 − 1 2 ∆ cost(T ). Denote r = root(T ). Let C be a centroid tree on T with cost(C) = cent(T ). Denote by v 0 , v 1 , . . . , v d = r the vertices along the path to r in C.

Upper bound
Finally, denote by p the minimal i for which one of the following holds: Note that from the third condition above it follows that p ≤ ∆. Denote P = (v 0 , . . . , v p ). We will prove the following. Assume for now that Claim 4.1 holds. Using Lemma 4.1, the fact that p ≤ ∆, the induction hypothesis and Claim 4.1, we have as required. It remains to prove Claim 4.1.
Proof of Claim 4.1. The proof breaks into three cases according to the defining condition of p.  Case 2. Assume s p ∈ V (T p+1 ). Denote by C 1 the set of connected components of T − P that are not contained in T p . Denote C 2 = C(T − P ) − C 1 (see Figure 3).
For vertices v ∈ V (T p −T p+1 ) we have {r, s p } ⊆ Path T (v). Therefore, using the fact that w(T p −T p+1 ) ≥ w(Tp) 2 , the contribution of vertices in V (T p ) to cost(T ) is at least Summing Equation (2) and Equation (3) yields the required result.
Case 3. Assume that there is a j < p such that K p = K j . Since p is minimal, we further assume that case 2 did not occur for indices smaller that p. In particular, s p = s j / ∈ V (T p ). As in case 2, the contribution of vertices in T − T p to cost(T ) is at least as in Equation (2). We have r / Figure 4). It follows that vertices in T p − T p+1 have both r and s p as ancestors. Since w(T p − T p+1 ) ≥ w(Tp) 2 , the contribution of vertices in T p is at least as in Equation (3). As in Case 2, the result follows by summing Equation (2) and Equation (3).
(i) There is a sequence of instances (T n , w n ) such that T n has maximum degree at most ∆, and for every centroid tree C n of (T n , w n ) lim n→∞ cost wn (C n ) OPT(T n , w n ) = 2 − 1 2 ∆ . (ii) There is a sequence of instances (T n , w n ) such that T n has maximum degree at most ∆, lim n→∞ OPT(T n , w n ) = ∞, w n (T n ) = 1, and for every centroid tree C n of (T n , w n ) Part (i). As in the proof of Theorem 1.2, it will suffice to prove Theorem 1.4(i) for some centroid tree C n . Using Lemma 2.4, we can then add arbitrarily small perturbation to w n , making C n the unique centroid tree. The sequence (T n , w n ) of Theorem 1.4(i) is constructed recursively as follows. For the sake of the construction we regard T n as a rooted tree. T 0 is simply a single vertex v (which is the root) and w 0 (v) = 1. For n > 0, T n is constructed from ∆ copies of T n−1 and ∆ + 1 additional vertices, v 1 , . . . , v ∆+1 , as shown in Figure 5 (left). The i'th copy of T n−1 gets the weight function w n−1 /2 i . We set w n (v i ) = 0 for 1 ≤ i ≤ ∆ and w n (v ∆+1 ) = 1/2 ∆ . Finally, we set root(T n ) = v 1 . By induction, T n has maximal degree ∆ and w n is a distribution on V (T n ).
Let C n be a search tree on T n defined recursively as follows. Connect the vertices v 1 , . . . , v ∆+1 to form a path and set v 1 as the root of C n . Continue recursively on each connected component of T − {v 1 , . . . , v ∆+1 }. (See Figure 5 (middle).) Observe that C n is a centroid tree of (T n , w n ). (4) Proof. Denote c n = cost wn (C n ). Clearly c 0 = 1 as required. Let n > 0. For each i, the subtree of all the descendants of v i in C n has weight 1/2 i−1 . Therefore It is straightforward to verify that the right hand side of Equation (4) is the solution to the recursive formula above.
In order to upper bound OPT(T n , w n ) we construct recursively a search tree T n on T n . For n > 0, T n is constructed by setting v ∆+1 as root and attaching to it ∆ copies of T n−1 . The vertices v 1 , . . . , v ∆ are finally attached as leaves of T n , each at it's unique valid place. See Figure 5 (right).
Proof. Denote t n = cost wn (T n ). We have t 0 = 1. For n > 0, t n obeys the recursive relation of which the right hand side of Equation (5) is the solution.
Proof of Theorem 1.4(i). Using Lemma 4.2 and Lemma 4.3, Observe that, as discussed in Section 1, in the construction of Theorem 1.4(i), OPT(T n , w n )/w n (T n ) is bounded.
Part (ii). To prove Theorem 1.4(ii), we repeat the recursive construction of Theorem 1.4(i) with a slight modification. As before, T 0 is a tree with a single vertex. For n > 0, (T n , w n ) is constructed from ∆ weighted copies of (T n−1 , w n−1 ) and ∆ − 1 additional vertices, v 1 , . . . , v ∆−1 , each with weight 0, as shown in Figure 6 (left). We set root(T n ) = v 1 .
As before, the search tree C n is defined by connecting the vertices v 1 , . . . , v ∆−1 to a path, setting v 1 as root and recursing on the remaining connected component. Observe that C n is a centroid tree of (T n , w n ). (See Figure 6 (middle).) The search tree T n is defined by setting v ∆−1 as root, attaching to it ∆ copies of T n−1 , then adding the vertices v 1 , . . . , v ∆−2 as leaves, each at its unique valid place. See Figure 6 (right).  Proof. Denote c n = cost wn (C n ) and t n = cost wn (T n ). Clearly c 0 = t 0 = 1. For n > 0 we have 1 2 i (t n−1 + 1) + 2 1 2 ∆−1 (t n−1 + 1) = 1 + t n−1 , and the lemma follows by induction.
Proof of Theorem 1.4(ii). The fact that lim n→∞ OPT(T n , w n ) = ∞ follows from Lemma 4.4 and Theorem 1.3 (or Theorem 1.1). Using Lemma 4.4 again, we have Using Lemma 2.4, for each n we can add small enough perturbation to w n such that C n is the unique centroid tree and the claimed bound holds.

Computing centroid trees
In this section, we show how to compute centroid trees using the top tree framework of Alstrup, Holm, de Lichtenberg, and Thorup [AHLT05]. Top trees are a data structure used to maintain dynamic forests under insertion and deletion of edges. Most importantly, they expose a simple interface that allows the user to maintain information in the trees of the forest. For this, the user only needs to implement a small number of internal operations. Alstrup et al. in particular show how to maintain the median of trees in O(log n) per operation, see Section 2 for the definition of the median. As mentioned before, if all edge-weights are 1, then medians are precisely centroids (see Lemma 2.3).
Theorem 5.1 ([AHLT05, Theorem 3.6]). We can maintain a forest with positive vertex weights on n vertices under the following operations: • Add an edge between two given vertices u, v that are not in the same connected component; • Remove an existing edge; • Change the weight of a vertex; • Retrieve a pointer to the tree containing a given vertex; • Find the centroid of a given tree in the forest.

Each operation requires O(log n) time. A forest without edges and with n arbitrarily weighted vertices can be initialized in O(n) time.
Note that Theorem 5.1 only admits positive vertex weights, whereas we allowed zero-weight vertices. We show how to handle this problem in Section 5.2.
We now show how to use Theorem 5.1 to construct a centroid tree in O(n log n) time.
Theorem 5.2. Given a tree T on n vertices and a positive weight function w, we can compute a centroid tree of (T , w) in O(n log n) time.
Proof. First build a top tree on T by adding the edges one-by-one, in O(n log n) time. Then, find the centroid c, and remove each incident edge. Then, recurse on each newly created tree (except for the one containing only c). The algorithm finds each vertex precisely once and removes each edge precisely once, for a total running time of O(n log n).

Output-sensitive algorithm
We now improve the algorithm given above to run in time O(n log h), where n is the number of vertices in T and h is the height of the computed centroid tree. The main idea of the algorithm is inspired by the linear-time algorithm for unweighted centroids by Della Giustina, Prezza, and Venturini [GPV19]. Instead of building a top tree on the whole tree T , we first split T into connected subgraphs of size roughly h, and build a top tree on each component. Contracting each component into a single vertex yields super-vertices in a super-tree. Each search for a centroid consists of a global search and a local search: We first find the super-vertex containing the centroid, then we find the centroid within that super-vertex. After finding the centroid, we remove it, which may split up the super-vertex into multiple super-vertices with a top tree each, and also may split the super-tree into a super-forest. Finally, we recurse on each component of the super-forest.
It can be seen that the total number of top tree operations needed is O(n). Since the top trees each contain only h vertices, a top tree operation takes O(log h) time, for a total of O(n log h). We now proceed with a more detailed description of the algorithm.
Ternarization. If the degree of a vertex of T is unbounded, then a partition into similarly sized connected subgraphs may not be possible. To fix this, we ternarize T by replacing each vertex v of degree d(v) larger than three by a path P v of d(v) − 2 vertices with degree three. Call the new vertices virtual and let T denote the resulting tree. Each virtual vertex of P v is incident in T to an (arbitrary) edge incident to v in T except for the two endpoints of P v that are incident to two such edges each. We maintain a link between each vertex in T and every associated virtual vertex in T (if any).
Let w be a weight function on T obtained from w by arbitrarily distributing weight from each deleted vertex to its associated virtual vertices. Note that T and w can be obtained from T and w , respectively, by contracting every group of associated virtual vertices. Further bserve that |V (T )| ≤ 2n.
Partition. Fix a parameter k. We now compute a partition into O( n k ) connected subgraphs of size at most 3k as follows. Arbitrarily root T . Iteratively remove minimal rooted subtrees of size at least k, using a simple linear-time bottom-up traversal. Since each node has at most three children, this produces connected subgraphs of size between k and 3k. The only exception are the nodes remaining at the end, which we put into a possibly smaller subgraph. The total number of subgraphs is at most 2n k + 1.
Building the super-tree. By contracting each connected subgraph of the partition into a single vertex, we obtain a tree T, the super-tree, and a weight function W . We call each vertex A ∈ V (T) a super-vertex, and write T Main procedure and recursion. Below, we describe how to find a centroid and remove it, along with associated virtual vertices. Doing so may split up T (and implicitly T and T ) into multiple connected components, on which we recurse. Hence, a recursive step operates on a tree T r (a subgraph of T ), a ternarization T r of T r , and a super-tree T r on T r . Note that only T r is explicitly given, whereas T r and T r are implicit in the super-tree data structure. Our task is to find a centroid c of T r and remove it from T r , i.e., for each component H of T r − c, we return a super-tree on a ternarization of H.
Finding centroids. We now describe how to find a centroid of T r using the super-tree T r . Note that, by Lemma 2.5, this is enough to find a centroid of T r .
First, we find the centroid A * of T r with the trivial linear scan described in the introduction. By Lemma 2.5, a centroid of T r must be contained in T r [A * ]. We now construct a suitable weight function w * on V (A * ) so that we can find a centroid of . Note that T r [A * ] and w * correspond to the tree and weight function obtained by contracting each C v into a single vertex. If C v = {v}, i.e., v is not a boundary vertex, then there are no contractions and w * (v) = w (v).
We compute w (C v ) for each boundary vertex v, and temporarily modify the weight of each v in the top tree on V (A * ) to match w * (v). Then, we find a centroid c of T r [A * ] w.r.t. w * , and undo the weight change. 5 By Lemma 2.5, a centroid of T r must be contained in C c . We also know a centroid must be contained in A * . Thus, by Lemma 2.2, a centroid must be contained in C c ∩ A * = {c}, so c must be a centroid of (T r , w ). If c is not virtual, it also is a centroid of (T r , w). If it is virtual, the linked non-virtual vertex in T r is a centroid of (T r , w). Splitting the data structure. We now remove c and its virtual vertices from T r and T r . Let R be the set of vertices to be removed. First, we remove each v ∈ R from its associated top tree by deleting all of its incident edges. This may split up each of the top trees into multiple new top trees. Each new top tree corresponds to a new super-vertex.
The creation of new super-vertices changes the super-tree, and may even split it up into a super-forest (see Figure 7 for an example). Let A be a super-vertex from which we removed a vertex. For each boundary vertex u of A, we find the new top tree that u belongs to. Using this, we can compute all super-edges incident to the new super-vertices (recall that each super-edge corresponds to a normal edge between two boundary vertices in different super-vertices). Finally, we compute the connected components of the new super-forest Recursion. After splitting, we recurse on each component of the super-forest that contains more than one (normal) vertex. Total running time. The preprocessing time is O(n log k), as desired.
Consider one search-and-split step. Let T r be the input tree, let T r be the input super-tree, let R be the set of vertices removed in the splitting step, and let F r be the super-forest produced after splitting. The time required to execute the step is Since each vertex is removed only once, the third term sums up to O(n log k) over all vertices. The second term can be charged to recursive calls (for each component of F r with more than one normal vertex) or single vertices (for each component of F r consists of only one normal vertex). It remains to bound the first term.
If T r consists of only one super-vertex A, then we charge the O(log k) cost to the centroid of T r [A], for a total of O(n log k) over the course of the algorithm.
We analyze the other recursive calls in rounds. Assume that in each round, we execute one step on each remaining super-tree, thereby finding all centroids on a certain level of the centroid tree. Let F 0 be the initial super-tree, and let F i be the forest of super-trees after round i. Note that the number of edges cannot grow by splitting, so each F i contains at most O( n k ) edges, and therefore at most O( n k ) non-isolated vertices, so the round requires O( n k log k) time in total. If the height of the tree is h, then we have precisely h rounds. Thus, the running time of the algorithm is O(( h k + 1)n log k).
In particular, if we know h and set k = h, then the running time is O(n log h). If we do not know h, we start with k = 2 and run the algorithm for k rounds. If it stops, then h ≤ k and we are done. Otherwise, try again with k ← k 2 . The last run of the algorithm, where h ≤ k ≤ h 2 , dominates the running time with O(n log h). Thus, we have Theorem 5.3. Let T be a tree on n vertices and w be a positive weight function. We can compute a centroid tree of (T , w) in time O(n log h), where h is the height of the computed centroid tree.

Spread and zero-weight vertices
Let w be a weight function on a tree T such that at least one vertex weight is positive. The spread of w is defined as σ w = w(T )/ min v∈V (T ),w(v)>0 w(v).
Let T be a centroid tree of (T , w). By definition, if u is a parent of v, then w(T v ) ≤ 1 2 w(T u ). More generally, if v is at depth d, then w(T v ) ≤ 2 −d w(T ). Thus, the depth of a positive-weight vertex v cannot be more than 1 + log w(T ) w(v) ≤ 1 + log σ w . In particular, if all vertex weights are positive, then the height of every centroid tree is at most 1 + log σ w , so the algorithm of the previous section runs in time O(n log log σ).
If we allow zero-weight vertices, however, then this is not necessarily true, since there could be a large unbalanced zero-weight subtree. Also, the top-tree component of our algorithm does not allow zero weights for technical reasons. We believe that the top tree implementation of [AHLT05] can be adapted to this changed requirement, but for a simpler presentation, we prefer to use the standard interface, as defined in [AHLT05].
The solution to both problems is to change the zero weights by a very small amount, as follows. Let T be a tree on n vertices, let w : V (T ) → R ≥0 , and let ε > 0. We define the positive weight function w ε : V (T ) → R + on G as follows: We now prove that a centroid tree of (T , w ε ) is also a centroid tree of (T , w) if ε is small enough. For this, it is enough to show that for every subgraph, no new centroids are introduced.
Lemma 5.1. Let T be a tree on n vertices, and let w : V (T ) → R ≥0 . For each small enough ε > 0, each centroid of (T , w ε ) is a centroid of (T , w).
Proof. Let k < n be the number of zero-weight vertices w.r.t. w. Let c be a centroid of (T , g) and let C ∈ C(T − c). We have If ε is small enough, this implies that w(C) ≤ 1 2 w(T ). Repeating the argument for each C ∈ C(T − c) shows that c is a centroid of (T , w).
Note that if all weights are integers, we can simply set ε = 1/n (or set ε = 1 and multiply each other weight by n). In general, we can treat ε symbolically, without explicitly computing a value for it.
We now show that the height of the centroid tree w.r.t. w ε is essentially bounded by the spread of w; in other words, replacing w with w ε ensures that the computed centroid tree is "reasonable". Note that we can ignore the spread of w ε here (which may be very large, if ε is very small).
Lemma 5.2. Let T be a tree on n vertices, let w : V (T ) → R ≥0 , and let ε > 0 be defined as in Lemma 5.1. Each centroid tree of (T , w ε ) has height O(log σ w + log n).
Proof. Let T be a centroid tree of (T , w ε ). By Lemma 5.1, T is also a centroid tree of (T , w). Thus, the depth of each node v with w(v) > 0 is at most 1 + log σ w . Now consider a subtree T u with w(T u ) = 0. Then the weight w.r.t. w ε of each node in T u is the same, so the spread of w ε restricted to V (T u ) is |V (T u )| ≤ n. This implies that the height of each zero-weight vertex in T is at most 2 + log σ w + log n, concluding the proof.
Lemmas 5.1 and 5.2 imply that we can replace w with w ε before running the algorithm. This yields Theorem 5.4 (Restatement of Thm. 1.5). Let T be a tree on n vertices and w be a weight function. We can compute a centroid tree of (T , w) in time O(n log h) ⊆ O(n log log (σ + n)), where h is the height of the computed centroid tree and σ is the spread of w. Handling many zero-weight vertices. If almost all vertices have weight zero, then Theorem 5.4 can be improved (in terms of σ) by a preprocessing stage. We briefly sketch the argument.
Let T be the given tree, and w be the given weight function. Let m be the number of vertices with positive weight, and note that σ w ≥ m. We first transform T by progressively removing zero-weight leaves, and replacing zero-weight degree-two vertices with an edge. This can be done with a single traversal in O(n) time.
In the resulting tree T , each zero-weight vertex has degree at least three (in particular, each leaf has positive weight). This means that at least half of the vertices in T have positive weight, so |V (T )| ≤ 2m. Computing a centroid tree T on T thus requires O(m log log(σ w + m)) = O(m log log σ w ) time with Theorem 1.5 or O(m log m) with Theorem 5.3. The latter bound is better when σ w ≥ 2 m .
It remains to show how to add the removed zero-weight vertices to the centroid tree T . Consider a maximal subgraph H of removed vertices. First compute a rooting T H of H; since all vertices in H have weight zero, T H is a centroid tree on H. Note that H has up to two neighbors in T , all with positive weight.
Let v be the neighbor of H that is farthest from the root in T , and attach T H to T as a child of v. It is not hard to see that this requires O(n) time in total, and that the resulting search tree is a centroid tree of (T , w). Thus, we have Theorem 5.5. Let T be a tree on n vertices and w be a weight function. We can compute a centroid tree of (T , w) in time O(n + m log log σ) or O(n + m log m), where m is the number of vertices in T with positive weight and σ is the spread of w.
In particular, since m ≤ σ, the running time becomes O(n) when σ ∈ O(n/ log log n).

Lower bounds on the running time
We start with our generic construction for a lower bound.
Lemma 5.3. Let k ≥ 1 and ≥ 1 be integers. There is a tree T k, on k · ( + 1) + 1 vertices and a class W k, of weight functions on V (T k, ) such that (ii) each w ∈ W k, has spread σ w ≤ k · 2 +1 ; (iii) for each w ∈ W k, , there is a unique centroid tree T w of (T , w), and T w has height at least + 1; (iv) for each pair of distinct w, w ∈ W k, , we have T w = T w .
Proof. Suppose first that k ≥ 2. Let T k, consist of a vertex c, and k stars of size + 1, with centers v 1 , . . . , v k adjacent to c. The remaining vertices in the star with center v i are denoted v i,1 , . . . , v i, , for all 1 ≤ i ≤ k. See Figure 8.
We claim that for any weight function w ∈ W, the centroid tree of (T k, , w) is unique, i.e., (iv) holds. Indeed, let w = w π1,...,π k , and observe that the unique centroid of T k, is c (since we assumed k ≥ 2). The removal of c splits T k, into the k stars with centers v 1 , . . . , v k . For all 1 ≤ i ≤ k, the centroid tree of the star with center v i is uniquely determined by the weight assignment by the permutation π i , and it is easily seen to be the path on vertices v i,1 , . . . , v i, in decreasing order of weights, followed by the star center v i . Finally, the entire search tree has height + 2, thereby (iii) holds.
In the case k = 1, we omit the vertex c and directly build a single star. Claims (i)-(iv) are easy to verify if we build W k, as above.
We are now ready to show our lower bounds.
Theorem 1.6. Let h ≥ 3 and n ≥ h + 1 be integers. Then there is a tree T on at most n vertices and a class W of weight functions on V (T ) such that for every w ∈ W, every centroid tree of (T , w) has height h, and every binary decision tree that solves T for W has height Ω(n log h).
Proof. We use Lemma 5.3 with k = n−1 h and = h − 1. The number of leaves in the decision tree is |W k, |, so its height is log |W k, | = log(( !) k ) ∈ Ω( n h log(h!)) = Ω(n log h). Theorem 1.6 implies that Theorem 1.5 is tight (up to a constant factor) for all n and h. A slight adaptation of the argument yields the following: Theorem 5.6. Let n ∈ N and σ ∈ R with 4n ≤ σ ≤ 2 n . Then there is a tree T on n vertices and a class W of weight functions on V (T ) with spread at most σ, such that every binary decision tree that solves T for W has height Ω(n log log( σ n )). Proof. We use Lemma 5.3 with = log σ − log n ≥ 2 and k = n ≥ 1. The spread of each w ∈ W k, is at most n · 2 σ n ≤ σ, as desired. The height of each decision tree is log |W k, | ∈ Ω( k log ) = Ω(n log log( σ n )). We now discuss for which range of the parameter σ the bounds in Theorems 5.5 and 5.6 are tight. First note that any reasonable model of computation will require Ω(n) time to read the input. Since we can pad the tree in the lower bound construction of Theorem 1.6 with zero-weight leaves, we can get a lower bound of Ω(n + m log log( σ m )) for all m ≤ n, where m is the number of positive-weight vertices. Note that σ ≥ m. If σ > 2 m , we can use Theorem 5.6 with σ = 2 m , and obtain a tight Θ(n + m log m) bound together with Theorem 5.5.
If σ ≤ 2 m and σ ≥ m · 2 log ε m for some constant ε > 0 (i.e., σ is very slightly superlinear in m), then log log( σ m ) ∈ Θ(log log σ), so we obtain a tight Θ(n + m log log σ) bound from Theorem 5.6 and Theorem 5.5. If σ is close to linear in m, then our upper bound O(n+m log log σ) and our lower bound Ω(n+m log log( σ m )) differ. We leave the problem of finding the correct bounds in this case as an open question.
6 Approximation guarantees of α-centroid trees 6.1 Upper bounds Part (i). The proof of Theorem 1.7(i) is a generalization of the proof of Theorem 1.1. We start with a lemma.
Lemma 6.1. Let c be a α-centroid of (T , w) and m = w(T ). Then OPT(H, w).
Proof. Let T a search tree on T . Denote r = root(T ). If r = c, the required follows using Observation 2.1. We assume therefore that r = c. Let H * ∈ C(T − c) such that r ∈ V (H * ). Repeating the argument of Lemma 3.1, we get where the second inequality follows since c is a α-centroid.
Proof of Theorem 1.7(i). By induction on the number of vertices. When |V (T )| = 1 we have as required.
Assume |V (T )| > 1. Repeating the argument of Theorem 1.1, using the induction hypothesis we get where the last inequality is exactly Lemma 6.1.
Proof. Let T be an arbitrary search tree on T . We will show that cost w (T ) is at least the right hand side of Equation (6). Denote r = root(T ). If r = c, the required follows using Observation 2.1, observing that m ≥ (2 − 3α)m + (3α − 1)w(c). Assume that r = c. Let  where the last inequality follows from c being an α-centroid and α ≤ 1 2 .
Case s = c. Let H 1 ∈ C(T − c) such that s ∈ V (H 1 ). Note that H 1 = H 0 . The contribution of vertices of H 1 to cost w (T ) is at least w(H 1 ) + cost w (T | H1 ), since these have r as predecessor. The contribution of c is at least 3w(c), since it has both r and s as predecessors. The contribution of all other vertices is bounded from below as in the previous case. Summing up, we get where the last inequality follows from c being an α-centroid. (See Figure 9.) Proof of Theorem 1.7(ii). By induction on the number of vertices. When |V (T )| = 1 we have as required.
Assume |V (T )| > 1. Repeating the argument of Theorem 1.1, using the induction hypothesis we get where the last inequality is exactly Lemma 6.2.

Lower bound
We show that Theorem 1.7(i) is tight when α ≥ 1 2 .
Theorem 1.8. For every α ∈ [ 1 2 , 1) there is a sequence of instances (T n , w n ) with lim n→∞ OPT(T n , w n ) = ∞, w n (T n ) = 1 and Proof. Let T n be defined recursively as in Theorem 1.2 and w n is defined recursively as follows. Let A, B and c be as in the definition of T n . Let w A and w B be weight functions on A and B respectively, each a copy of w n−1 . Then w n is given by Let C n and T n be the same search trees on T n as in the proof of Theorem 1.2. Observe that C n is an α-centroid tree on T n . With a similar analysis as in Theorem 1.2, we get cost wn (C n ) = n + 1 and cost wn (T n ) = (1 − α)n + 1. From these the required bound follows. Using Theorem 1.7(i), we have lim n→∞ OPT(T n , w n ) = ∞.

Optimal STTs
In this section we prove the characterization of optimal STTs as α-centroid trees.
Theorem 1.9. Let T be an optimal STT of (T , w). Then, T is a 2 3 -centroid tree of (T , w). For the purpose of proving Theorem 1.9, we define the following transformation on search trees. Let T be a search tree on T and v ∈ V (T ). We denote by T v the search tree on T that is obtained as follows. Set root(T v ) = v. The subtrees of T v rooted at the children of v are all the trees of the form T | H , where H ∈ C(T − v). We say that T v is obtained from T by lifting the vertex v. (This transformation can also be defined via rotations, e.g., see [BCI + 20]. T v is obtained by repeatedly rotating the edge between v and its parent until v becomes the root.) For every u, v ∈ V (T ) we have Proof of Theorem 1.9. Let T be an optimal STT on T , and suppose towards contradiction, that T is not a 2 3 -centroid. Assume w.l.o.g., that w(T ) = 1. By taking T to be a minimum height counterexample, we can assume that the root x of T has a child y, so that w(T y ) > 2 3 . Let B x denote the set of vertices not in the same component of T − x as y, and let B y denote the set of vertices not in the same component of T − y as x. Finally, let B x,y = V (T ) − B x − B y . By our assumption, w(B y ∪ B x,y ) > 2 3 , and thus, w(B x ) < 1 3 . We distinguish three cases.
contradicting the optimality of T . If Case 1 did not occur, we have w(B x,y ) > 1 3 , and in particular, B x,y = ∅. Denote by z the unique child of y in B x,y . Case 3. Finally, assume that z is not in the path between x and y. Note that this cannot happen in the special case of BSTs, i.e., when T is a path. Let t ∈ B x,y be the unique vertex in T whose removal separates x, y and z to different components. Now, transform T by lifting t. As in the previous case, depths of vertices in B x increase by one, depths of vertices in B y stay the same and depths of vertices B x,y decrease by at least one. To see this, observe that each vertex in B x,y gains t as ancestor and loses two ancestors from {x, y, z}, and possibly more. (See Figure 10.3.) As in the previous case, we have cost w (T t ) < cost w (T ), a contradiction.

Conclusions
We showed that the average search time in a centroid tree is larger by at most a factor of 2 than the smallest possible average search time in an STT and that this bound is tight. We also showed that centroid trees can be computed in O(n log h) time where h is the height of the centroid tree.
Perhaps the most intriguing question is to determine whether the problem of computing an optimal STT is in P. A secondary goal would be to achieve an approximation ratio better than 2 in near linear time. (The running time of the STT's of Berendsohn and Kozma [BK22] degrade as O(n 2k+1 ) for a 1 + 1 kapproximation.) As for centroid trees, a remaining question is whether they can be computed in O(n) time whenever the spread of the weight function is σ ∈ O(n).
A special case in which high quality approximation can be efficiently found is when an α-centroid tree exists for α < 1 2 . This case can be recognized and handled in near linear time using our algorithm. (Observe that an α-centroid tree for α < 1 2 is also the unique 1 2 -centroid tree.) Theorem 1.7(ii) gives strong approximation guarantees for this case, yielding the optimum when α ≤ 1 3 . It is an interesting question whether the bounds can be improved for α in the range 1 3 , 1 2 , i.e., whether Theorem 1.7(ii) is tight. A small gap remains in the exact approximation ratio of centroid trees when T has maximum degree ∆ and OPT is unbounded, i.e., between the upper bound (2 − 1 2 ∆ ) of Theorem 1.3 and the lower bound (2 − 4 2 ∆ ) of Theorem 1.4(ii). On the other hand, let c be a centroid of (T , w), and let u ∈ V (T ) − {c}. We show that W (u) ≥ W (c). Let c = u 1 , u 2 , . . . , u k = u be the path from c to u in T . We claim that W (u i ) ≤ W (u i+1 ) for all i ∈ [k − 1]. This in particular implies W (c) ≤ W (u), as desired.
Towards our claim, let i ∈ [k − 1], and let H i be the component of T − u i+1 that contains u i (see Figure 11). Note that H i encompasses c and all but one component of C(T − c), so w(H i ) ≥ 1 2 w(T ). For ). This concludes the proof C Tie-breaking Lemma 2.4. Let T be a tree, w : V (T ) → R ≥0 a weight function and let C be a centroid tree of (T , w). For every ε > 0 there exists a weight function w : V (T ) → R ≥0 such that C is the unique centroid tree of (T , w ) and w − w ∞ < ε.
We prove Lemma 2.4 by the following series of simple observations. Observation C.1. Let w 1 , w 2 : V (T ) → R ≥0 be two weight functions. Assume that a vertex c ∈ V (T ) is a centroid of both (T , w 1 ) and (T , w 2 ). Assume further that c is the unique centroid of (T , w 2 ). Then c is the unique centroid of (T , w 1 + w 2 ).
Proof. Denote W i (u) = v∈V (T ) d T (u, v) · w i (v). If c is a minimum of W 1 and is the unique minimum of W 2 , then it is the unique minimum of W 1 + W 2 , and by Lemma 2.3 it is a unique centroid of (T , w 1 + w 2 ).
Observation C.2. Let w : V (T ) → R ≥0 and m = w(T ). If w(u) ≥ m/2 then u is a centroid of (T , w). Moreover, if w(u) > m/2, then u is the unique centroid of (T , w).
Proof. u is a centroid since the total weight of T − u is ≤ m/2. Assume w(u) > m/2 and let v = u. The connected component of T − v in which u is has weight > m/2, therefore v is not a centroid.
Observation C.3. Let T be a search tree on T . There exists a w : V (T ) → R ≥0 such that T is the unique centroid tree of (T , w).
Proof. By induction on n. When n = 1 every w has the desired property. Assume n > 1. Let r = root(T ) and let T 1 , . . . , T d be the subtrees of T rooted at the children of r. Let T i = T [V (T i )]. By the induction hypothesis there are w i : V (T i ) → R ≥0 such that T i is the unique centroid tree of (T i , w i ). Let w : V (T ) → R ≥0 be defined by