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))–1.\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.

$◻$ (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)))$$