Prolog binary list issue

Question

I'm working on a binary tree program in Prolog. The specific issue I'm having is with traversals. Here's what I have :

inOrder(bttree(_,L,_),T):-  inOrder(L,T).
inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T).
inOrder(bttree(_,_,R),T):-  inOrder(R,T).

I've been querying it with:

inOrder(bttree(20,
    bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)) bttree(30)), T).

so the output SHOULD be:

[5,10,15,20,30];
false.

But when I run it, it just returns false. I'm fairly certain the problem is in my use of append/3, but I simply can't work it out. If anyone can help, it'd be much appreciated

Answer 1

I get rather an infinite loop for the query (note the missing comma in your original query):

?- inOrder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30)), T).
   loops.

And I get the same infinite loop, even after adding goals false into your program. The resulting program is called a failure-slice:

inOrder(bttree(_,L,_),T):- false, inOrder(L,T).
inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T), false.
inOrder(bttree(_,_,R),T):-  false, inOrder(R,T).

So this remaining clause alone causes this loop. In fact, any query with a node bttree/3 will now loop, even

 ?- inOrder(bttree(20, nil,nil), T).
    loops.

So we need to fix at least that remaining visible part.

Not that clauses are read independently of each other, so your first clause reads:

inOrder(bttree(_,L,_),T):- inOrder(L,T).

So the inorder traversal of a node will be just the inorder traversal of a the left subtree. That does not seem right.

What you actually want is to describe them together. The best way is not to use append/3 but rather a dcg:

inorder(nil) --> [].
inorder(bttree(N,L,R)) -->
   inorder(L),
   [N],
   inorder(R).

Now we get:

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30))), T).
   false.

Again, false! But this time it is this bttree(30) which should be replaced:

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30,nil,nil))), T).
   T = [5,10,15,20,30].