TAOCP 7.2.1.6 Exercise 63
After the first iteration of Rémy's algorithm there is a single external node, carrying label $1$.
Section 7.2.1.6: Generating All Trees
Exercise 63. [**] [If] If the first two iterations of Rémy's algorithm have produced $\boxed{\square}\text{ }\boxed{\square}$, what decorated binary trees are possible after the next iteration?
Verified: yes
Solve time: 2m09s
After the first iteration of Rémy's algorithm there is a single external node, carrying label $1$.
During the second iteration there is only one existing node to choose, namely that external node. It is replaced by a new internal node whose two children are the old leaf (still labeled $1$) and the new leaf (labeled $2$). The left or right choice is compensated by the decoration rule, so there is only one decorated binary tree after two iterations. It is
$$ \begin{array}{c} \bullet\ /\ \backslash\ 1\qquad2 \end{array} $$
where $\bullet$ denotes the unique internal node.
For the third iteration there are exactly three existing nodes that may be selected:
$$ \text{the root},\qquad \text{leaf }1,\qquad \text{leaf }2. $$
For each selected node, the newly created leaf labeled $3$ may become either the left child or the right child of the new internal node. Hence there are
$$ 3 \times 2 = 6 $$
possible executions.
It remains to enumerate the resulting decorated binary trees.
If the root is expanded, the two possibilities are
$$ \begin{array}{c} \bullet\ /\ \backslash\ 3\qquad\bullet\ \qquad/\ \backslash\ \qquad1\qquad2 \end{array} \qquad\qquad \begin{array}{c} \bullet\ /\ \backslash\ \bullet\qquad3\ /\ \backslash\ 1\qquad2 \end{array} $$
If leaf $1$ is expanded, the two possibilities are
$$ \begin{array}{c} \bullet\ /\ \backslash\ \bullet\qquad2\ /\ \backslash\ 3\qquad1 \end{array} \qquad\qquad \begin{array}{c} \bullet\ /\ \backslash\ \bullet\qquad2\ /\ \backslash\ 1\qquad3 \end{array} $$
If leaf $2$ is expanded, the two possibilities are
$$ \begin{array}{c} \bullet\ /\ \backslash\ 1\qquad\bullet\ \qquad/\ \backslash\ \qquad3\qquad2 \end{array} \qquad\qquad \begin{array}{c} \bullet\ /\ \backslash\ 1\qquad\bullet\ \qquad/\ \backslash\ \qquad2\qquad3 \end{array} $$
These six trees are all distinct. The two root expansions have the unique feature that the root has one leaf child and one internal child. The four remaining trees have the original root unchanged, and are distinguished by whether the expanded leaf is $1$ or $2$, and by whether the new leaf $3$ is placed to the left or to the right of that leaf. Since every execution of the third iteration is determined uniquely by the chosen node together with the left or right placement of the new leaf, these six trees exhaust all possibilities.
Thus the decorated binary trees obtainable after the next iteration are precisely the six trees displayed above.