Binary Tree Isomorphism

Question

I have an assignment to write among other things, a set of prolog predicates that determine if any two binary tree's are isomorphic to each other. The predicate must also be able to provide all of the isomorphic graphs to any given binary tree.

Here is what I have so far, it works except for returning duplicates.

% Clause: btree_iso
%
% Specification:
% --------------
% Satisfied when the two binary-tree parameters are isomorphic. Two binary
% trees are isomorphic if one can be derived from the other by changing the
% order of the branches. Either of the parameters may be instantiated with a
% variable when btree_iso is used in a top-level goal.
%
% Description:
% ------------
% Base case for the binary tree iso morphism predicate.
% Both sides are leaves.
btree_iso( leaf, leaf ).

% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTL2 ),
                                                             btree_iso( BTR1, BTR2 ).
% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTR2 ),
                                                             btree_iso( BTR1, BTL2 ).

Expected Output:

? - btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

My Output

?- btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

Obviously these are all repeats, I can't seem to find an appropriate location to place the cut so the predicate does not return duplicates. I also tried write two other predicates for a node with only one leaf, and one other node but they didn't seem to help.

Any advice as to how I can stop the duplicates?

Answer 1

Why don't you ask your TA?

Honestly, you'll do better in class if you try to figure this out for yourself.

Answer 2

Think about what happens when BT = node(leaf, X, leaf). Your solution yields two identical solutions for this case. One where the leaves are swapped and one where they are not.

You need to explicitly handle this case, returning only one solution. Since this case will probably look like the other clauses, you'll also need to ensure that this case can't be satisfied by more than one clause.