output a binary tree in preorder as a list in prolog

Question

I am trying to create a list as output for a binary tree in prolog here is my code so far.

preorder(node(R, empty, empty),[R]).
preorder(node(R,Lb,Rb),[R|Ys]) :- preorder(Lb, Ys).
preorder(node(R,Lb,Rb),[R|Ys]) :-preorder(Rb, Ys).

My thought being that you traverse the tree and add the R to the rest list Ys. it doesnt work as intendet though

?- preorder(node(1,node(2,empty,empty),node(3,empty,empty)),Z).
Z = [1, 2] ;
Z = [1, 3] ;
false.

This is the query I try to run and what I get. Prolog gives me all possible ways to the leafs, but I want just one list with all values in preorder, so basically the 2 lists combined([1,2,3]).

Answer 1

You can use the following code:

preorder(T, L) :-
    preorder(T, [], L).

preorder(empty, L, L).
preorder(node(R, Lb, Rb), L0, [R|L2]) :-
    preorder(Rb, L0, L1),
    preorder(Lb, L1, L2).

Examples:

?- preorder(node(1,node(2,empty,empty),node(3,empty,empty)), L).
L = [1, 2, 3].

?- preorder(empty, L).
L = [].

?- preorder(node(1, empty, empty), L).
L = [1].

?- preorder(node(1,node(2,node(3,empty,empty),node(4,empty,empty)),node(5,empty,empty)), L).
L = [1, 2, 3, 4, 5].