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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.