This also allows me to construct $2^{ {m \choose 2}}$ valid rooted trees on $2^m$ vertices, as David Speyer predicted.

I think it's reasonable to conjecture that these are the only solutions.

Edit: A variant of this argument in different language was given by Gerhard Paseman in the comments. I didn't read it very carefully and didn't understand his language.

This also allows me to construct $2^{ {m \choose 2}}$ valid rooted trees on $2^m$ vertices, as David Speyer predicted.

I think it's reasonable to conjecture that these are the only solutions.

Here's an equivalent formulation of this conjecture:

Every valid tree with more than one vertex admits a nontrivial automorphism.

Under this assumption, we can inductively prove that every valid tree has the stated form.

First, note that no valid tree has an automorphism with a fixed vertex. We could take that point to be the root, and then the function $i_v$ would be automorphism-invariant and hence would not be injective.

Second, recall that every automorphism of a tree fixes either a vertex or an edge.

Given a nontrivial automorphism that fixes an edge, its square fixes both vertices on that edge. So its square must be trivial, because the tree has no nontrivail automorphisms with fixed points. Hence it is an involution that exchanges the two sides of the edge.

It remains to check that each side of the edge is individually a valid tree with $n/2$ vertices. But this is easy - for an automorphisms $\sigma$, the function $i_{\sigma(v)}-i_v$ is constant, and equal to $n/2$ for both sides of the fixed edge, hence equal to $n/2$ everywhere. Since distinct vertices have distinct $i-v$ modulo $n$, it follows that distinct vertices have distinct $i_v$ modulo $n/2$ unless they are mirror images, sodistinct vertices on the same side have distinct $i_v$ mod $n/2$ and hence each side s a valid tree on $n/2$ vertices.

This shows it comes from one step of my construction, applied to a valid tree. By induction, it comes from an iteration of my construction, starting with the $1$-vertex tree.

One can use this idea, and the fact that the only automorphism-free trees on $\leq 8$ vertices are the one-vertex tree, $E_7$, and $E_8$, to find all valid trees on $\leq 8$ vertices without a brute force search.

However, I don't see any possible way to prove a valid tree has an automorphism.

Here is a reformulation of the problem that might be interesting:

Following David Speyer's improvement, given a rooted tree on $n$ vertices, we number each vertex $v$ with an integer $i_v$ mod $n$ so that the root is numbered $0$ and, if vertex $v_1$ is a child of vertex $v_2$ then $i_{v_1}$ is $i_{v_2}$ plus the number of descendants of $v_1$ (including $v_2$).

We say a rooted tree is valid if all the vertices $v$ have distinct numbers $i_v$. Each solution to the frog-jumping puzzle with $n$ lilies gives a valid rooted tree.

I've just noticed a simplification:

We can express the condition "if vertex $v_1$ is a child of vertex $v_2$ then $i_{v_1}$ is $i_{v_2}$ plus the number of descendants of $v_1$ (including $v_2$)." in a way that does not involve the root. Given two vertices of a tree, connected by an edge, each vertex of the tree is on one side of the edge or the other. The descendants on the child vertex are exactly on that side, so saying $i_{v_1}=i_{v_2}$ plus descendents of $v_1$ is equivalent to saying that $i_{v_1}$ is $i_{v_2}$ plus the number of the $v_1$ side, which is equivalent to saying that $i_{v_2}$ is $i_{v_1}$ plus the number on the $v_2$ side, as the numbers on both sides add up to $n$.

One consequence of this is that the validity of a rooted tree does not depend on the root.

This also allows me to construct $2^{ {m \choose 2}}$ valid rooted trees on $2^m$ vertices, as David Speyer predicted.

The argument proceeds by induction. Given a valid rooted tree $T$ on $2^m$ vertices, fix a vertex $v \in T$ and consider $T \cup T$, with the two copies connected $v$ to $v$, with only the root in the first $T$ preserved. This numbering will have the property that for $w$ in one copy of $T$ and $w'$ its mirror image in the other copy of $T$, $i_{w}= i_{w'} + 2^m$ - using the local description we can see the difference $i_w-i_{w'}$ is independent of $w$, and by setting $w=v$ we see the difference is $2^m$. This immediately implies the $i_w$ are different modulo $2^{m+1}$ - to be equal mod $2^{m+1}$, $i_{w_1}$ and $i_{w_2}$ must first be equal mod $2^m$, which implies because $T$ is valid that $w_1$ and $w_2$ are either equal or mirror images, hence equal.

If there are $2^{{m\choose 2}}$ trees on $2^m$ vertices, and we have $2^m$ choices for which vertex to join them at, this gies a total of $2^{{m\choose 2}+m}= 2^{{m+1 \choose 2}}$ possibilities on $2^{m+1}$ vertices.

It is easy to see that we don't double count here. Any tree has at most one edge with an equal number of vertices on both sides, so every tree arises from this construction in at most one way.

I think it's reasonable to conjecture that these are the only solutions.

My previous post:

Here is a reformulation of the problem that might be interesting: