Prolog - Check if two binary trees are equivalent

I would like to know how to check if two binary trees are equivalent in SWI-Prolog.

I tried:

equivalent(nil, nil).
equivalent(t(N,L1,R1), t(N,L2,R2)):- equivalent(L1,L2), equivalent(R1,R2).

but it does not work.

Solution

I assume that by "equivalence", you mean that two trees are equivalent if they each contain the same ordered set of data nodes, with possibly different root nodes.

To test for that sort of equivalence requires either:

Traversing the trees in parallel and depth-first and comparing each node, or
Flattening each tree into an ordered list (the worst-case, degenerate form of a binary tree, where the nodes are inserted in order), and then comparing the two lists.

I would suggest the latter approach, because the implementation is much simpler.

Given a binary tree t(Payload,Left_Children,Right_Children) where the atom nil indicates the empty tree, flattening a binary tree into a linked list is as easy as this:

flatten( nil      , [] ) .
flatten( t(P,L,R) , Ps ) :-
  flatten(L,Ls),
  flatten(R,Rs),
  append(Ls,[P|Rs],Ps)
  .

And comparing two trees for equivalence is as easy as

equivalent(T1,T2) :- flatten(T1,L), flatten(T2,L) .

The two trees are equivalent if the both flatten into the same list.

Another, perhaps simpler/more performant method of flattening a binary tree uses a predicate that visits each node in order and uses findall/3 to coalesce that into a list.

Visiting nodes in order is easy. Beginning with the root node,

Recursively visit the left subtree, then
Visit the current node, and finally
Recursively visit the right subtree

Something like this:

flatten(T,Ps) :- findall(P, visit(T,P), Ps ) .

visit( t(_,L,_) , P ) :- visit(L,P) .
visit( t(P,_,_) , P ) .
visit( t(_,_,R) , P ) :- visit(R,P) .