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

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.

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.