Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is ${E}_{n}$-computable, $n\ge 3$, if each vertex has its number of children bounded by an ${E}_{n}$ function. So this rules out trees which grow sideways a lot quicker than they grow in height, but it has to be *a lot* quicker.

Let $T$ be an ordered, plane recursive tree. The *height* of a vertex is its geodesic distance from the root node. A *breadth-first search* of $T$ is a labelling of the vertices which begins at the root node, then visits all the vertices of height 1 in order (left to right), then the vertices of height 2, and so on.

Suppose there is a function $f$ such that $f(n)$ is the number of direct children of the vertex with label $n$. Then we can define the following functions:

- $\delta (n)$ is the number of vertices of height $n$,
- $\iota (n)$ is the label of the leftmost vertex of height $n$,
- $\tau (n)$ is the label of the leftmost vertex of height $n$,
- $h(v)$ is the height of the vertex with label $v$,
- $p(v)$ is the label of the parent of the vertex with label $v$.

## Lemma 1

$\delta $, $\iota $ and $\tau $ are ${E}_{3}$-computable.

### Proof

Define $\delta $, $\iota $ and $\tau $ as follows:

$$\begin{array}{rcl}\delta (0)& =& 1,\\ \delta (n+1)& =& \sum _{i=\iota (n)}^{\tau (n)}.\\ \\ \iota (0)& =& 0,\\ \iota (n+1)& =& \iota (n)+\delta (n).\\ \\ \tau (n)& =& (\sum _{i=0}^{n}\delta (n))\u20131.\end{array}$$

Note that $\delta (n)$ and $\iota (n)$ are both bounded by $\tau (n)+1$, so we only need to show $\tau (n)$ is bounded by an ${E}_{3}$ function.

Let $\sigma (n)=\underset{i\le n}{sup}({x}_{i})$, an ${E}_{3}$ function. Then $\tau (n)\le \tau (n-1)\cdot (\sigma (\tau (n-1))+1)$. So it looks like this is bounded by some number of compositions of factorial, but I’m considerably less sure about that than when I began this post. Certainly, if the number of children of each vertex of height $n$ is $n!$, then $\tau (n)$ is bounded by $n!!$. I should definitely know more about sums of series than I do.

$\u25fb$ (maybe)

Once those are defined, we can give definitions of $h$ and $p$:

$$h(v)=\underset{i<v}{\mu}(v\le \tau (i))$$

$$p(v)=\stackrel{\tau (h(v)-1)}{\underset{i=\iota (h(v)-1)}{\mu}}(\sum _{j=\iota (h(v)-1)}^{i}{x}_{j}<v-\iota (h(v)))$$