# Computing RF Tree Distance over Succinct Representations
## 3 Methodology
### Robinson-Foulds Distance Computation
Since each permutation can be represented with \((1+\varepsilon)n\log n\) bits, allowing for finding \(\pi[i]\) in constant time and \(\pi^{-1}[i]\) in \(O(1/\varepsilon)\) time [23], we obtain a more compact representation than the previous construction. In what follows, for simplicity, we consider the mapping representation through an array of integers. Then, the algorithm counts the number of clusters present in both trees. This is achieved by examining the first tree in a post-order traversal and verifying, for all clusters, whether they are present in the second tree. To verify whether a cluster from the first tree is present in the second tree, the key idea is to obtain the cluster from the second tree that is described by the lowest common ancestor (LCA) among all the taxa present in that cluster. Then, if the number of taxa present in the cluster that was obtained is equal, we can guarantee that the cluster is present in both trees. For example, we consider \(T_{4}\) and \(T_{5}\) as the trees represented in Figures 4 and 5, respectively. To verify whether the cluster highlighted in \(T_{4}\), namely \(\{A,B\}\), is present in \(T_{5}\), we first need to calculate the index of both taxa \(A\) and \(B\). In the balanced parentheses representation of \(T_{4}\), \(A\) and \(B\) occur in positions 4 and 5, respectively. Then, using the map, we can conclude that in balanced parentheses representation of \(T_{5}\), \(A\) and \(B\) occur in positions 9 and 7, respectively. Then, by computing the LCA in \(T_{5}\) between those nodes, index 6 is obtained, which represents the cluster highlighted in \(T_{5}\). Given that, this cluster contains three leaves and the original one contains just two, and thus it can be concluded that cluster \(A,B\) is not present in \(T_{5}\). To efficiently compute this distance, the trees are traversed in a post-order traversal. This is performed to guarantee that all nodes are accessed before their ancestors. This way, it is possible to minimize the number of times that the LCA operation is called. For example, considering \(T_{4}\) as the tree represented in Figure 4. As mentioned before, when computing the LCA between nodes \(A\) and \(B\), the value of which is 6, we can conclude that the cluster is not present on tree \(T_{5}\). When computed, each LCA value is saved on a stack associated to the node with index 3 of \(T_{4}\). Figure 5: Tree \(T_{5}\) and its balanced parentheses representation. (**a**) A rooted labelled phylogenetic tree \(T_{5}\) with labels on leaves; \(u_{1},u_{2},u_{3}\) and \(u_{4}\) are unlabelled internal nodes. (**b**) Node index enumeration for \(T_{5}\), where the node number denotes its index; the highlighted cluster is the smaller one containing A and B. (**c**) The balanced representation of \(T_{5}\); each pair of parentheses correspond to a unique node in the tree; \(i_{o}\) and \(i_{c}\) denote the opening and the closing parenthesis for the node with index \(i\), respectively. Continuing the post order, we now obtain for taxa \(C\) that its position in \(T_{4}\) is 6 and, consulting the map, its position in \(T_{5}\) is 10. Then, to check whether cluster \(A,B,C\) is also present in \(T_{5}\), we use the LCA stored in a node with index 3 of \(T_{4}\), i.e., 6 and Position 10 to compute the new LCA value. The new LCA value is also in Position 6 and is saved on a stack associated to the node with index 2 of \(T_{4}\). Since in this case the cluster obtained in \(T_{5}\) has the same number of leaves as cluster \(A,B,C\) in \(T_{4}\), we can conclude, by construction, that it is the same cluster. This process continues until it reaches the tree root. We notice that when there are only labels on the leaves, the internal nodes are not included in clusters. In our approach, we do not count the singleton clusters, since they occur in both trees. Moreover, the internal nodes of each tree offer us the number of non-singleton clusters present on that tree.