title: Binary Tree Isomorphism
body: <p>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. </p>
  
  <p>Here is what I have so far, it works except for returning duplicates. </p>
  
  <pre><code>% 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 ).
  </code></pre>
  
  <p><strong>Expected Output:</strong> </p>
  
  <pre><code>? - 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)).
  </code></pre>
  
  <p><strong>My Output</strong></p>
  
  <pre><code>?- 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)).
  </code></pre>
  
  <p>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.</p>
  
  <p>Any advice as to how I can stop the duplicates?</p>