Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.

To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.

In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.

From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?"

You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is replicate, which takes a value $v$ and size $n$, then creates a finger tree of size $n$ containing $n$ copies of $v$. The real work of replicate is done in applicativeTree, which has individual cases for $n \leq 8$ and recurses for larger $n$.

StackExchange Computer Science Q#41081, answer score: 4