# Computing RF Tree Distance over Succinct Representations
## 4 Implementation
### Distance Calculation
#### 4.2.1 Robinson-Foulds Using PostOrderSelect  
To make sure that the tree is traversed in a post-order traversal, this implementation simply performs a loop from 1 to \(n\) and calls the function PreOrderSelect for all the values. This implementation also uses a very similar strategy to the one used in the Day algorithm Day (1976) to keep the LCA results computed earlier. This strategy consists in using a stack that keeps track, for each node, of the index of the corresponding cluster from the second tree and the size of the cluster from the first tree. Then, whenever a leaf is found, the corresponding index is added, as well as the size of the leaf, which is one. When the node found is not a leaf, it moves through the stack and finds the last nodes that where added until the sum of their sizes is equal to the size of the cluster. For these nodes, the LCA between each pair is computed while removing them from the stack. When this process is finished, it is possible to verify whether that cluster is present in the other tree and then add the information of that cluster to the stack so that the computations of the LCA that where performed are not performed again. An implementation of this process can be seen in Algorithm 2. Despite the strategy of using a stack being similar to that of the Day algorithm, our approach just stores in Stack 2 integers for each node, while in the Day algorithm, it is necessary to store 4 integers for each node, namely the value of the left leaf; the value of the right leaf; the number of leaves below; and the size of the cluster. Moreover, with our approach, there is no need to create the cluster table as the Day algorithm need since we use the LCA to verify the clusters. Given that the algorithm moves through each node in the first tree and needs to compute LCA, PostOrderIndex and number of leaves NumLeaves from each cluster, the theoretical complexity of the algorithm is \(O(n\log(n))\), with \(n\) being the number of nodes in each tree. ```
1:Input:\(T_{1}\),\(T_{2}\) in Neweick format. 2:Output:\(bv_{1}\),\(bv_{2}\),\(w_{1}\),\(w_{2}\),\(CodeMap\),\(weightsSum\)\(\triangleright\)\(w_{1}\), \(w_{2}\) and \(weightsSum\) are only used for wRF and weRF distances
3:\(HashTable\gets null\)
4:\(weightsSum\gets 0\)
5:for\(i=1;i<3;i++\)do
6:\(bv_{i}\gets null\)
7:\(index\gets 0\)
8:\(s\gets null\)\(\triangleright\)\(s\) is a stack of integers
9:while\(c\leftarrow\) getChar\((T_{i})\
eq\);do
10:if\(c=^{\prime}\) (\({}^{\prime}\)then
11:\(push(s,index)\)
12:\(index\)++
13:\(push\_back(bv_{i},1)\)
14:elseif\(c=^{\prime}\),then
15:continue
16:elseif\(c=^{\prime}\))\({}^{\prime}\)then
17:\(c\leftarrow\) getChar\((T_{i})\)
18:ifnot\((c=^{\prime})\) or \(c=^{\prime}\) (\({}^{\prime}\) or \(c=^{\prime}\),\({}^{\prime}\) or \(c=^{\prime}\),\({}^{\prime}\)) then
19:if\(c=:\)then
20:\(c\leftarrow\) getChar\(()\)
21:\(weight\leftarrow\) getWeight\((T_{i})\)
22:\(w_{i}[index]\gets weight\)
23:\(weightsSum\gets weightsSum+weight\)
24:else
25:\(label\leftarrow\) getLabel\((T_{i})\)
26:if\(i=1\)then
27:\(HashTable[label]\gets index\)
28:else
29:\(CodeMap[HashTable[label]]\gets count\)
30:endif
31:endif
32:else
33:\(c\leftarrow\) ungetChar\((T_{i})\)
34:endif
35:\(pop(s)\)
36:\(push\_back(bv_{i},0)\)
37:else
38:\(push\_back(bv_{i},1)\)
39:\(push\_back(bv_{i},0)\)
40:\(label\leftarrow\) getLabel\((T_{i})\)
41:if\(i=1\)then
42:\(HashTable[label]\gets index\)
43:else
44:\(CodeMap[HashTable[label]]\gets count\)
45:endif
46:endif
47:endif
48:endwhile
49:endfor
50:\(\text{free}(HashTable)\)
51:Return\(bv_{1},bv_{2},w_{1},w_{2},CodeMap,weightsSum\)
```  
**Algorithm 1** Parsing Phase
```
1:Input\(bv_{1},bv_{2},CodeMap\)
2:\(\triangleright\) Let \(numInternalNodes1\) and \(numInternalNodes2\) be the number of internal nodes of both trees.