# How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?

any help is appreciated.

• This is a very straightforward application of recursion. I suggest making sure that you understand recursion. Once you do, you would be able to solve it on your own. Commented Apr 2, 2020 at 14:21
• What do you call "generate", more precisely ?
– user16034
Commented Apr 19, 2023 at 12:49
• @YuvalFilmus: straightforward ? Are you sure ?
– user16034
Commented Apr 19, 2023 at 12:50

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<Tree> perm(vertex x):
if x is leaf:
return x
Let C be the set of all children of x.
Set<Tree> result <- 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