# Nearest Embedded and Embedding Self-Nested Trees
## 3 Height Profile of the Tree Structure  
### Definition and Complexity  
This section is devoted to the definition of the height profile \(\rho_{\tau}\) of a tree \(\tau\) and to the presentation of an algorithm to calculate it. In the sequel, we assume that the tree \(\tau\) is always traversed in the same order, depth-first search to set the ideas down. In particular, when vectors are indexed by nodes of \(\tau\) sharing the same property, the order of the vector is important and should be always the same.  
Given a vertex \(v\in\mathcal{V}(\tau)\),  
\[\gamma_{h}(v)=\#\left\{v^{\prime}\in\mathcal{C}_{\tau}(v)\,:\,\mathcal{H}( \tau[v^{\prime}])=h\right\}\]  
is the number of subtrees of height \(h\) directly under \(v\). Now, we consider the vector  
\[\rho_{\tau}(h_{1},h_{2})=\left(\gamma_{h_{2}}(v)\,:\,v\in\mathcal{V}(\tau),\, \mathcal{H}(\tau[v])=h_{1}\right)\]  
made of the concatenation of the integers \(\gamma_{h_{2}}(v)\) over subtrees \(\tau[v]\) of height \(h_{1}\) ordered in depth-first search. Consequently, \(\rho_{\tau}\) is an array made of vectors with varying lengths.  
Let \(A_{1}\) and \(A_{2}\) be two arrays for which each entry is a vector. We say that \(A_{1}\) and \(A_{2}\) are equivalent if, for any line \(i\), there exists a permutation \(\sigma_{i}\) such that for any column \(j\),  
\[A_{1}(i,j)=\sigma_{i}(A_{2}(i,j)).\]  
In particular, \(i\) being fixed, all the vectors \(A_{1}(i,j)\) and \(A_{2}(i,j)\) must have the same length. This condition defines an equivalence relation. The height profile of \(\tau\) is the array \(\rho_{\tau}\) as an element of the quotient space of arrays of vectors under this equivalence relation. In other words, the vectors \(\rho_{\tau}(h_{1},h_{2})\), \(0\leq h_{2}<h_{1}\) and \(h_{1}\) fixed, must be ordered in the same way but the choice of the order is not significant. Finally, it should be already remarked that \(\rho_{\tau}(h_{1},h_{2})=\emptyset\) when \(h_{2}\geq h_{1}\) or \(h_{1}>\mathcal{H}(\tau)\). Consequently, the height profile can be reduced to the triangular array  
\[\rho_{\tau}=\left[\rho_{\tau}(h_{1},h_{2})\right]_{0\leq h_{2}<h_{1}\leq \mathcal{H}(\tau)}.\]  
The application \(\rho_{\tau}\) provides the distribution of subtrees of height \(h_{2}\) just below the root of subtrees of height \(h_{1}\) for all couples \((h_{1},h_{2})\), which typically represents the height profile of \(\tau\). For clarity's sake, we give the values of \(\rho_{\tau_{k}}\) for the trees \(\tau_{k}\) of Figure 1, coefficient \((i,j)\) of the matrix being \(\rho_{\tau_{k}}(i,j-1)\),  
\[\rho_{\tau_{1}}=\rho_{\tau_{2}}=\left[\begin{array}{cccc}(1,1,2)&\emptyset &\emptyset\\ (0,1,1)&(1,1,1)&\emptyset\\ (0)&(0)&(3)\end{array}\right]\quad\text{and}\quad\rho_{\tau_{3}}=\left[ \begin{array}{cccc}(1,1,1)&\emptyset&\emptyset\\ (1,1,1)&(1,1,1)&\emptyset\\ (0)&(0)&(3)\end{array}\right]. \tag{1}\]  
It should be noticed that the height profile does not contain all the topology of the tree since trees \(\tau_{1}\) and \(\tau_{2}\) of Figure 1 are different but share the same height profile (1). However, the height of a tree \(\tau\) can be recovered from its height profile through the relation \(\mathcal{H}(\tau)=\text{dim}(\rho_{\tau})\), the dimension of \(\rho_{\tau}\) being defined by  
\[\text{dim}(\rho_{\tau})=\min\ \left\{n\geq 0\,:\,\forall\,i\geq 0,\,\rho_{ \tau}(n+1,i)=\emptyset\right\}.\]  
**Proposition 2**.: \(\rho_{\tau}\) _can be computed in \(O(\#\mathcal{V}(\tau)\times\mathcal{D}(\tau))\)-time._  
Proof.: First, attribute to each node \(v\in\mathcal{V}(\tau)\) the height of the subtree \(\tau[v]\) with complexity \(O(\#\mathcal{V}(\tau))\). Next, traverse the tree in depth-first search in \(O(\#\mathcal{V}(\tau))\) and calculate for each vertex \(v\) the vector \((\gamma_{h}(v))_{0\leq h<\mathcal{H}(\tau[v])}\) in \(\#\mathcal{C}_{\tau}(v)\leq\mathcal{D}(\tau)\) operations. Finally, append this vector to \(\rho_{\tau}(\mathcal{H}(\tau[v]),\cdot)\) component by component.