Online binary tree creation via $a\to ax$ and $ab\to a(bx)$

Question

I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties:

• $T_n$ has $n$ leaves
• $T_n$ is well balanced (height $\lg n+O(1)$)
• $T_n$ is obtained from $T_{n-1}$ by one of the two operations $t\to (t,\ast)$ or $(t,t')\to (t,(t',\ast))$

In other words, we are limited to right insertion and rotation at the root. Ideally, the sequence $T_n$ should also have a simple recursive form for any $n$. Is it possible?

Originally, I attempted to use the sequence $T_1=\ast$, $T_n=(T_k,T_{n-k})$ where $k$ is the largest power of 2 less than $n$, but I believe that it is not possible, since $T_8$ cannot be obtained from $T_7$ by the two operations, and one would need an infinite number of deeper operations like $(a,(b,(c,d)))\to(a,(b,(c,(d,\ast))))$ to get the whole sequence. Furthermore, an exhaustive enumeration shows that $T_8$ in this sequence (the perfect binary tree on 8 leaves) is not obtainable, although there are some trees with height 4 in the sequence, so perhaps $\lg n+O(1)$ is not impossible.

Answer 1

We can characterize the trees that are constructible as follows. If $T_n=(a,b)$, then both $a$ and $b$ must be subtrees of every following $T_k$, $k>n$, because neither of the two operations can split them. So let $A_n$, $B_n$ be sequences defined as $T_n=(A_n,B_n)$ (for $n>1$). In the base case we have $A_2=B_2=\ast$, and at each following step we either have $A_{n+1}=(A_n,B_n)$ and $B_{n+1}=\ast$ or $A_{n+1}=A_n$ and $B_{n+1}=(B_n,\ast)$.

In particular, $B_n$ can only ever be $\ast$ or $(B_{n-1},\ast)$, so $B_n$ must be a left leaning path like $(((\ast,\ast),\dots,\ast),\ast)$. Similarly, $A_n$ consists of a left leaning path with $B_i$'s hanging off it as in $(((\ast,B_{i_k}),\dots,B_{i_2}),B_{i_1})$, so it has a restricted structure.

Let a $B$ tree mean a tree which has only leaves coming off the left spine, and an $A$ tree is a tree with $B$ trees coming off the left spine. Note that $T_n$ is also an $A$ tree.

Unfortunately, $A$ trees are not even balanced up to a constant factor: they are at best height $\Omega(\sqrt n)$. A $B$ tree with $n$ leaves has height exactly $n-1$, so the heaviest $A$ tree of height $k$ has the form $(((\ast,B_1),B_2),\dots,B_k)$ (where the subscript is now being used to indicate the number of elements in the $B$ tree), and this has $1+1+2+\dots+k=\frac{k(k+1)}{2}+1=O(k^2)$ leaves, so any $A$ tree with $n$ leaves has height at least $\Omega(\sqrt n)$.

This generalizes to the case of deeper rules like $(a,(b,c))\to(a,(b,(c,\ast)))$. In this case, we find that $T$ has the form $(A,(B,C))$ where $C$ has $*$ off the left spine, $B$ has $C$ off the left spine, and $A$ has $B$ off the left spine (so $C$ is a $B$ tree and $B$ is an $A$ tree in our previous terminology). By a similar argument, we find that $T$ can have at most $O(k^3)$ leaves for height $k$, so it has height at least $\Omega(\sqrt[3]{n})$, and in general, with $m$ such rules you get height at least $\Omega(\sqrt[m]{n})$, so optimal balance is not possible.