Swapping binary trees in prolog

Question

This is exercise 3.5 from Learn Prolog Now. They put it before explaining lists so I need a procedure that doesn't involve lists.

The task is to swap the leaves of nested binary trees. If the query is

swap(tree(tree(leaf(1), leaf(2)), leaf(4)), T).

the answer should be

T = (tree(leaf(4), tree(leaf(2), leaf(1))).

With

swap((X, Y), (Y, X)).

swap(tree(X, Y), T) :- 
   swap((X, Y), (Y, X)), 
   T = (Y, X).

I get

T = (leaf(4), tree(leaf(1), leaf(2))).

As you see the leaf(1) and leaf(2) didn't get swapped. I want some hints or even your procedure and it should work with any depth of the nodes. Thanks.

Answer 1

You have a base case swap a leaf, and a general case swap a tree! For a leaf, nothing to do :

swap(leaf(X), leaf(X)).

When you swap a tree, you must swap its leaves too, so

swap(tree(X,Y), tree(Y1,X1)) :-
    swap(X,X1),
    swap(Y,Y1).