How to generate tree variants of a tree using recursion?
The outline is: You start the function-call at the root vertex. For every child-vertex, you find all permutations of its sub-tree. Then you you find all combinations of these permuations of the children's sub-trees, and for each of them do all permutations of the child-vertices themselves.
The recursion happens where you need the permutations of the sub-trees of the children.
The exit-condition is the call on a leaf.

Set&lt;Tree&gt; perm(vertex x):
    if x is leaf:
        return x
    Let C be the set of all children of x.
    Set&lt;Tree&gt; result &lt;- emptySet
    For all different combinations of perm(c) from the vertices c of C, now called comb:
        For all permutations p of C:
            add to result the graph you get with comb and p.
    return result