Code in Prolog generate all structurally distinct full binary trees with n node

Question

generate all structurally distinct full binary trees with n leaves in Prolog. The problem is given the number of leaves, output all distinct full binary trees. 'Full' here means any internal node must have two children, left and right.

Answer 1

To build all the trees through backtracking:

full_tree(Leaves, [LTree, RTree]):-
  Leaves > 1,
  TLeaves is Leaves-1,
  between(1, TLeaves, LLeaves),
  RLeaves is Leaves-LLeaves,
  full_tree(LLeaves, LTree),
  full_tree(RLeaves, RTree).
full_tree(1, '.').

This recursive procedure has a base case that unifies the second argument with '.' when number of leaves is 1. The recursive step applies when the number of leaves is greater than 1. It splits this number in two non-zero new numbers which sum the number of leaves and calls itself to build the left and right branches.

Then this procedure will dump all trees to console:

dump_all_trees(Leaves):-
  full_tree(Leaves, Tree),
  dump_full_tree(Tree),
  nl,
  fail.
dump_all_trees(_).

dump_full_tree([LTree, RTree]):-
  write('('),
    dump_full_tree(LTree),
    dump_full_tree(RTree),
  write(')'),
  !.
dump_full_tree(Leaf):- write(Leaf).

Test case:

?- dump_all_trees(4).
(.(.(..)))
(.((..).))
((..)(..))
((.(..)).)
(((..).).)