Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by $$ \textrm{lca}(u,v) = \text{the lowest common ancestor of $u$ and $v$} $$ for all vertices $u,v$ belonging to the same tree.

Given $k$ vertices from a tree, I can apply my LCA operator to all pairs of vertices and thereby obtain new vertices to which I can apply the LCA operator once again etc. etc. In this way we construct a tree that contains the $k$ original vertices and has at most $2k-1$ vertices in total (easy to see).


  • If the $k$ vertices are all leaves in a full, binary tree, then the constructed tree is the full, binary tree tree with $2k-1$ vertices.
  • If the $k$ vertices all belong to the same path, then the constructed tree is just a path of length $k$.

How many different trees can be constructed in this way from $k$ vertices using the LCA operator?

Said differently (in a labeled version which is OK): How many rooted trees are there with $k$ labeled vertices and all other vertices being generated from those $k$ vertices using an LCA operator?

An asymptotic formula or a good lower bound would be fine.

  • 1
    $\begingroup$ For asymptotics, an upper bound on the number of k generated semilattices may help you. For labeled elements, the number is something like doubly exponential ($2^{2^k}$). For lower bounds look at general tree enumeration and consider trees wth k leaves and k+n vertices for n much smaller than k. Gerhard "Ask Me About System Design" Paseman, 2013.05.24 $\endgroup$ – Gerhard Paseman May 25 '13 at 6:40
  • 1
    $\begingroup$ An upper bound with a double exponential looks very big to me. After all, there are at most $(2k-1)^{2k-3}$ labeled trees with $2k-1$ nodes. I have already looked at some enumeration results, but none of them give me exactly what I am looking for. I have now added another way of stating my question. $\endgroup$ – Esben May 25 '13 at 8:42

Your Answer

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

Browse other questions tagged or ask your own question.