How to replace every occurence of a value with another one in a binary tree with Prolog

I have a problem with my code and I can not figure out why it does not work for me. It stops at the first occurens and just replaces one occurens. The task is to replace every occurence of a value with another one in a binary tree like the example below.

Thats a example tree:

testTreeReplace(t2, tree(a,tree(1,tree(a,tree(6,-,-),tree(9,-,-)),-),tree(8,-,tree(a,tree(20,-,-),tree(3,-,-))))).

and thats the code I use:

replace(X,Y,TreeIn,TreeOut) :-
    testTreeReplace(TreeIn,T),
    replaceH(X,Y,T,TreeOut).

replaceH(X,Y,tree(X,L,R),tree(Y,L,R)).

replaceH(X,Y,tree(A,L,R),tree(A,L,New)) :-
    replaceH(X,Y,R,New).

replaceH(X,Y,tree(A,L,R),tree(A,New,R)) :-
    replaceH(X,Y,L,New).

and the ouput is:

?- replace(a,b,t2,Res).
Res = tree(b, tree(1, tree(a, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(a, tree(20, -, -), tree(3, -, -)))) ;
Res = tree(a, tree(1, tree(a, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(b, tree(20, -, -), tree(3, -, -)))) ;
Res = tree(a, tree(1, tree(b, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(a, tree(20, -, -), tree(3, -, -)))) ;
false.

but it should be

Res = tree(b, tree(1, tree(b, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(b, tree(20, -, -), tree(3, -, -)))).

(all the a's should be b's)

Further more I dont want to use additional librarys. Thank you in advance

Solution

You should not branch in the recursion, since that means that in one of the answers, you will only replace the element (if it matches), in another answer you will recurse on the left subtree, and in another one in the right subtree.

We can thus first make a predicate that checks if Z is equal to X and in case it

replaceValue(X, Y, Z, R) :-
    (  X == Z
    -> R = Y
    ;  R = Z
    ).

Then we can thus make a predicate that will for a tree try to replace the value of the tree, and in the same branch also replaces Xs by Ys in the left and right subtree:

replaceTree(X,Y,tree(Z, L, R),tree(Z2, L2, R2)) :-
    replaceValue(X, Y, Z, Z2),
    replaceTree(X, Y, L, L2),
    replaceTree(X, Y, R, R2).
replaceTree(_, _, -, -).

This thus gives us:

?- replaceTree(a, b, tree(a, tree(1, tree(a, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(a, tree(20, -, -), tree(3, -, -)))), T).
T = tree(b, tree(1, tree(b, tree(6, -, -), tree(9, -, -)), -), tree(8, -, tree(b, tree(20, -, -), tree(3, -, -)))) ;
false.