# Nearest Embedded and Embedding Self-Nested Trees
## 3 Height Profile of the Tree Structure
### Relation with Self-Nested Trees  
Self-nested trees are characterized by their height profile considering the following result. **Proposition 3**: \(\tau\) _is self-nested if and only if, for any \(0\leq h_{2}<h_{1}\leq\mathcal{H}(\tau)\), all the components of the vector \(\rho_{\tau}(h_{1},h_{2})\) are the same (for instance see the profile (1) of the tree \(\tau_{3}\) presented in Figure 1). In addition, a self-nested tree \(\tau\) can be reconstructed from \(\rho_{\tau}\) (see Algorithm 1)._  
Proof. : If \(\tau\) is self-nested, the \(N_{h_{1}}\) subtrees of height \(h_{1}\) appearing in \(\tau\) are isomorphic and thus have the same number \(n_{h_{1},h_{2}}\) of subtrees of height \(h_{2}\) just below their root. Consequently,  
\[\rho_{\tau}(h_{1},h_{2})=(\underset{N_{h_{1}}}{\longleftarrow}\underset{N_{ h_{1}}}{\longleftarrow}).\]  
The reciprocal result may be established considering the following lemma which proof presents no difficulty. **Lemma 1**: _If all the subtrees of height \(0\leq h<H\) appearing in a tree \(\tau\) are isomorphic, and if all the subtrees of height \(H\) have the same number of subtrees of height \(0\leq h<H\) just below their root, then all the subtrees of height \(H\) appearing in \(\tau\) are isomorphic._  
All the subtrees of height \(1\) in \(\tau\) are isomorphic because all the components of \(\rho_{\tau}(1,0)\) are the same. The expected result is shown by induction on the height thanks to the previous lemma which assumptions are satisfied since \(\rho_{\tau}\) always contains vectors for which all the entries are equal. The previous reasoning also provides a way (presented in Algorithm 1) to build a unique (self-nested) tree \(\mathcal{T}\) from the height profile \(\rho_{\tau}\). In addition, this is easy to see that \(\tau\) and \(\mathcal{T}\) are isomorphic. To present the algorithm of reconstruction of a self-nested tree from its height profile, we need to define the restriction of a height profile to some height. Let \(p\) be a height profile. The restriction \(p_{|_{h}}\) of \(p\) to height \(h\geq 0\) is the array defined by  
\[\left\{ \begin{array}{ll}\forall\,1\leq h_{1}\leq h,&\forall\,h_{2}\geq 0, \quad p_{|_{h}}(h_{1},h_{2})=p(h_{1},h_{2}),\\ \forall\,h_{1}>h,&\forall\,h_{2}\geq 0,\quad p_{|_{h}}(h_{1},h_{2})= \emptyset.\end{array} \right.\]  
Consequently, \(\dim(p_{|_{h}})=\min(dim(p),h)\). A peculiar case is \(p_{|_{0}}\) for which each entry is the empty set and thus \(\dim(p_{|_{0}})=0\). It should be also remarked that there may exist no tree \(\tau\) such that \(p_{|_{h}}\) is the height profile of \(\tau\). ```
1 FunctionSN(\(p\)): Data: a height profile \(p\) such that all the components of \(p(h_{1},h_{2})\) are the same Result: the unique self-nested tree \(\tau\) such that \(\rho_{\tau}=p\)\(\tau=\bullet\)for\(i\) from \(0\)to\(\dim(p)-1\)doaddSN(\(p_{|_{i}}\)) as child of \(\mathcal{R}(\tau)\)\(p(\dim(p),i)_{1}\) times return\(\tau\)
```  
**Algorithm 1**Construction of a self-nested tree from its height profile. As we can see in the proof of Proposition 3 or in Algorithm 1, the lengths of the vectors \(\rho_{\tau}(h_{1},h_{2})\) are not significant to reconstruct a self-nested tree \(\tau\). Consequently, since all the components of \(\rho_{\tau}(h_{1},h_{2})\) are the same, we can identify the height profile of a self-nested tree with the integer-valued array \([\rho_{\tau}(h_{1},h_{2})_{1}]\). **Proposition 4**. : _The number of nodes of a self-nested tree \(\tau\) can be computed from \(\rho_{\tau}\) in \(O(\mathcal{H}(\tau)^{2})\)._  
Proof. : By induction on the height, one has \(\#\mathcal{V}(\tau)=\mathcal{N}(\mathcal{H}(\tau))\), where the sequence \(\mathcal{N}\) is defined by \(\mathcal{N}(0)=1\) (number of nodes of a tree reduced to a root) and,  
\[\forall\,1\leq H\leq\mathcal{H}(\tau),\;\mathcal{N}(H)=1+\sum_{h=0}^{H-1}\rho_ {\tau}(H,h)\mathcal{N}(h). \tag{2}\]  
The number of operations required to compute \(\mathcal{N}(\mathcal{H}(\tau))\) is of order \(O(\mathcal{H}(\tau)^{2})\).