prolog traverse nonstandard tree left to right

Question

I need to implement a predicate trav(Tree,List) that performs a left to right tree traversal;

Where: Tree is defined by the structure node(left,right), where left and right can be either another node or any Prolog data item. List is the list of leaf node values in the tree.

For example:

?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .

What I have so far:

trav(tree,[ ]).
trav(node(Left,Rigth), L) :-
    trav(Left, L),
    trav(Right, L),
    append(Left,[Left|Right],L).

Answer 1

My Prolog is slightly rusty, but I believe that this should do it:

node(Left, Right).

trav(node(Left, Right), L) :- 
  trav(Left, L1), 
  trav(Right, L2),
  append(L1, L2, L).
trav(X, [X]) :- X \= node(A, B).

Intuitively, trav(Left, L1) says traverse the left subtree, storing each element in L1. trav(Right, L2) says traverse the right subtree storing each element in L2. Lastly, append(L1, L2, L) append the two lists, L1 and L2 into list L. For a leaf, trav(X, [X]), puts X into a singleton list as long as it does not unify with a node.