# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Final Output and Possible Solution Sets
This implies (via Claim 7) that \(h_{1}=h_{2}=h\), completing the proof of Statements 1 and 2 in the general case for the original trees \(G\) and \(S\). Finally, we need to prove Statements 3 and 4 for original trees \(G\) and \(S\). We have proved that \((q_{3}^{\prime},h_{3}^{\prime})\) is a potential rooting of \(G_{A}\) with respect to \(S_{A}^{(3)}\) and that \(h_{3}^{\prime}=h\). We will prove that \((q_{3}^{\prime},h)\) is also a potential rooting of \(G\) with respect to \(S^{(3)}\). Consider a leaf \(a\). If \(a\in A\), then we already know from \(G_{A}\) that \(d_{G}(q_{3}^{\prime},a)=d_{S}(r_{3},a)+h\). We still need prove the same equality for \(a\in B\). Consider points \(u\) and \(x\) as in Claim 8; the claim implies that \(d_{S}(x,r_{1})=d_{G}(u,q_{1})\). Point \(x\) may be located either between \(r_{1}\) and \(r_{3}\) or between \(r_{3}\) and \(r_{2}\). We will assume the latter; the former is proved analogously by switching the roles of \(r_{1}\) and \(r_{2}\). Point \(u\) is then located between \(q_{3}\) and \(q_{2}\), as thanks to Claim 8, the distances along paths from \(r_{1}\) to \(r_{2}\) and from \(q_{1}\) to \(q_{2}\) are preserved. Finally, we obtain  
\[d_{S}(a,r_{3}) = d_{S}(a,r_{1})-d_{S}(r_{1},r_{2})\] \[= d_{G}(a,q_{1})-h-d_{G}(q_{1},q_{3}^{\prime})\] \[= d_{G}(a,q_{3}^{\prime})-h.\]  
The previous claim broadly characterizes the full set of solutions; the next one observes a useful property of solutions located on a single edge of \(S\). **Claim 10**. : _Let \(G\) and \(S\) be unrooted trees. Let \(\{x,y\}\) be an edge in \(S\) and let \([\alpha_{1},\alpha_{2}]\) be an interval such that every point \(S(x,y,\alpha)\) for \(\alpha\in[\alpha_{1},\alpha_{2}]\) is a potential root of \(S\). Then there is an edge \(\{u,v\}\) in \(G\) and interval \([\beta_{1},\beta_{2}]\) such that when we root \(S\) in the potential root \(S(x,y,\alpha)\) for \(\alpha\in[\alpha_{1},\alpha_{2}]\), its corresponding potential rooting \((q,h)\) has the form \(q=G(u,v,\beta)\) for \(\beta\in[\beta_{1},\beta_{2}]\)._  
Proof. : Our discussion in Section 2.5 implies that potential rootings of \(G\) corresponding to a single edge of \(S\) form an interval on some path, that is, they can be expressed as \(G(a,b,\beta)\). It remains to prove that the interval of possible values of \(\beta\) is within one edge of \(G\). This is implied by Claim 8, where as \(r_{1}\) and \(r_{2}\), we use the endpoints \(S(x,y,\alpha_{1})\) and \(S(x,y,\alpha_{2})\), and as \(q_{1}\) and \(q_{2}\) the endpoints in the corresponding interval in \(S\). Since the path between \(r_{1}\) and \(r_{2}\) is within a single edge of \(S\), point \(x\) for any leaf will be either \(r_{1}\) or \(r_{2}\). This implies that point \(u\) will be either \(q_{1}\) or \(q_{2}\). As a result, there is no node on the path between \(q_{1}\) and \(q_{2}\), where the paths to other leaves branch out. As tree \(G\) has all internal nodes of degree at least 3, \(q_{1}\) and \(q_{2}\) must be located on a single edge. Claims 9 and 10 are important for the final part of our algorithm, in which we transform the solution to the final form. As we have seen in the proof of Claim 10, the potential roots of \(G\) for a single edge of \(S\) are specified within an interval on some path. Thanks to Claim 10, we know that they are in fact located on a single edge. Our goal is now to algorithmically find this edge \(\{u,v\}\) in \(G\) and the interval \([\beta_{1},\beta_{2}]\). To keep the running time \(O(N)\), we want to avoid doing such computation for each edge of \(S\) individually. Instead, we use the connected nature of the set of solutions in both \(S\) and \(G\) implied by Claim 9. We traverse tree \(S\) by a depth-first search, and the first time we encounter an edge with a non-empty set of potential roots, we find the corresponding edge in \(G\); even a naive \(O(N)\)-time search is sufficient. Each time we encounter another edge \(\{x,y\}\) of \(S\) with a non-empty solution set, we have already seen some adjacent edge \(\{x,z\}\) with a solution.