PreOrder Tree Traversal in Prolog

Question

I have this Prolog predicate for PreOrder traversal of a tree:

preOrder(nil, []).
preOrder(node(X, nil, nil), [X]).
preOrder(node(X, L, _), [X|T]) :- preOrder(L, T).
preOrder(node(X, _, R), [X|T]) :- preOrder(R, T).

The problem is, it returns an incomplete list. For example, I get:

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

When it should be L=[1,2,3,4,5].

Why is it stopping short?

Answer 1

Look at the answers Prolog produces. It's not a single one:

?- preOrder(node(1,node(2,node(3,nil,nil),node(4,nil,nil)),node(5,nil,nil)),L).
   L = [1,2,3]
;  L = [1,2,3]
;  L = [1,2,3]
;  L = [1,2,4]
;  L = [1,2,4]
;  L = [1,2,4]
;  L = [1,5]
;  L = [1,5]
;  L = [1,5]
;  false.

Each of your rules describes some part independently of the others. But you need to describe them all together.

The best way to solve this is to use DCGs

Answer 2

It is stopping short because you have two recursive clauses, each one goes just to one side of the tree. You also have two base cases although the second one is not needed.

So you'd remove the second clause and join the two recursive clauses in only one clause which appends the results from both branches.

E.g.:

preOrder(nil, []).
preOrder(node(X, L, R), [X|T]) :- 
  preOrder(L, LT), 
  append(LT, RT, T), 
  preOrder(R, RT).

You can also use an accumulator for the traversal:

preOrder(Tree, List):-
  preOrder(Tree, [], RList),
  reverse(RList, List).

preOrder(nil, List, List).
preOrder(node(X, L, R), List, NList) :- 
    preOrder(L, [X|List], MList), 
    preOrder(R, MList, NList).

Note that as one commenter said, these definitions for preOrder no not work right to generate trees given a traversal.

You may want to use DCGs to define a procedure that will be reversible, internally using open lists:

preOrder(nil)-->[].
preOrder(node(X, L, R))-->[X], preOrder(L), preOrder(R).

And you would call it using phrase/2:

?- phrase(preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil))), L).
L = [1, 2, 3, 4, 5].