# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Computation of Potential Rootings  
In the first phase of the algorithm, we will compute potential rootings of all rooted subtrees of \(S\). Claim 3 gives the potential rooting of a subtree with one leaf, and Claim 4 allows us to compute the potential rooting of a bigger subtree from rootings of its two subtrees. Let \(T\) be a rooted subtree of \(S\). The point \(q\) in a potential rooting \((q,h)\) of \(G_{L(T)}\) will be represented in the algorithm as \(G(a,b,\alpha)\) for some leaves \(a\) and \(b\) and distance \(\alpha\). We will also keep a set of representative leaves for each subtree with a potential rooting \((q,h)\). The size of this set will be the same as the degree of \(q\) in \(G_{L(T)}\). For each edge \(\{q,u\}\) incident to \(q\) in \(G_{L(T)}\), the set will contain a leaf \(a\) such that \(\text{between}_{G}(q,u,a)\) is true; that is, the path from \(q\) to \(a\) uses edge \(\{q,u\}\). Note that if \(q\) is not a node of \(G\), but rather a point inside some edge \(e\), we will assume that \(G\) was modified by subdividing \(e\) in this point, and thus the degree of \(q\) is two, and it has two incident edges. The algorithm processes each rooted subtree \(T\) of \(S\) in the bottom-up order. As a special case, if \(G_{L(T)}\) consists only of leaf \(a\), the rooting will be represented as \((q,0)\), where \(q=G(a,a,0)\), and the representative set is \(\{a\}\). Consider now rooted subtree \(T\) with two rooted subtrees \(S_{1}\), \(S_{2}\) as in Claim 4; we will also use other notation from the claim. The rooting for subtree \(T\) is computed from already known rootings of \(S_{1}\) and \(S_{2}\) as follows. * Compute \(h\) using Condition 1 of Claim 4. This requires computing \(d_{G}(q_{1},q_{2})\), where \(q_{1}\) and \(q_{2}\) are represented as \(q_{1}=G(a_{1},b_{1},\alpha_{1})\) and \(q_{2}=G(a_{2},b_{2},\alpha_{2})\) for some leaves \(a_{1}\), \(b_{1}\), \(a_{2}\), \(b_{2}\). This distance computation is one of our tree primitives (see Sections 2.2 and 2.8). * Compute \(\beta\) from Condition 2; check that \(0\leq\beta\leq d_{G}(q_{1},q_{2})\). Then represent point \(q=G(q_{1},q_{2},\beta)\) in the form \(G(a,b,\alpha)\) where \(a,b\in\{a_{1},b_{1},a_{2},b_{2}\}\). This computation is also one of our primitives. * To check Condition 3, we use the sets of representative leaves \(A_{1}=\{a_{1},\ldots,a_{g}\}\) and \(A_{2}=\{b_{1},\ldots,b_{h}\}\) for \(q_{1}\) and \(q_{2}\), respectively. We also build the set \(A\) for \(q\) (see Figure 4). If \(q_{1}=q_{2}\), Condition 3 is satisfied, and \(q=q_{1}=q_{2}\). To build the set \(A\), we start with the union of \(A_{1}\) and \(A_{2}\). This clearly covers all outgoing edges from \(q\) belonging to \(G_{L(T)}\), but some of them may be covered twice, if they are shared between \(G_{L(S_{1})}\) and \(G_{L(S_{2})}\). Thus, if for some \(a_{i}\in A_{1}\) and \(b_{j}\in A_{2}\) we have that \(\text{between}_{G}(a_{i},q,b_{j})\) is false, either \(a_{i}\) or \(b_{j}\) is excluded from \(A\). Now let us assume that \(q\
eq q_{i}\) for some \(i\in\{1,2\}\); let \(j\) be the other index from \(\{1,2\}\). We need to check that the edge \((q_{i},u)\) leaving from \(q_{i}\) towards \(q\) and \(q_{j}\) does not belong to \(G_{L(S_{i})}\). This is achieved by checking that for each leaf \(a\in A_{i}\) the predicate \(\mathsf{between}_{G}(a,q_{i},q_{j})\) is true (see Figure 5). If neither \(q_{1}\) nor \(q_{2}\) equal \(q\), this check is repeated for both values of \(i\). To build the set \(A\) for \(q\), we consider two cases: if \(q\) is one of the endpoints of the path between \(q_{1}\) and \(q_{2}\), say \(q=q_{1}\), then we start with set \(A_{1}\) and add to it one leaf from \(A_{2}\) as a representative of the edge leaving from \(q_{1}\) towards \(q_{2}\). Finally, if \(q\) is inside the path connecting \(q_{1}\) and \(q_{2}\), its degree in \(G_{L(T)}\) will be two and the set \(A\) will consist of one arbitrarily chosen leaf from each \(A_{1}\) and \(A_{2}\).