Counting trees

Cayley’s formula for the number of trees $T_n$ on $n$ vertices says that $T_n = n^{n-2}$. There are many proofs of this formula. One of them constructs a bijection between the set of all trees on $n$ vertices and the set of all sequences of length $n-2$ on $n$ letters. But how to derive this if we do not know in advance that the result should be $n^{n-2}$?

One possible appraoch goes as follows.