Prolog in-order traversal

Question

Example of the node looks like:

node(3, nil, 14).
node(14, nil, 15).
node(15, nil, 92).

I have seen similar questions asked here however mine is different as my nodes have 3 instead of 2 values in the parameter.

Example of how it should run:

?- inOrder(3, X).
X = [3, 14, 15, 35, 65, 89, 92] .

My current code is:

 % the in-order traversal of a leaf is the leaf
 inOrder(X, [X]) :-
    node(X, nil, nil).

 % if the node only has a left child, we traverse that
 inOrder(x, [X|T]) :-
    node(X, L, [X|T]),
    inOrder(L, T).
 % if the node only has a right child we traverse that
 inOrder(x, [X|T]) :-
    node(X, nil, R),
    inOrder(R, T).
 % if the node has both, we traverse them both.
inOrder(x, [X|T]) :-
    node(L, X, R),
    L \= nil, R \= nil,
    inOrder(L, T1),
    inOrder(R, T2),
    append(T1, T, T2).

It returns false instead of an actual value.

Answer 1

There are several twists in your representation. In general, treelike structures are not flattened out in the database, here with node/3, but rather maintained in a single term.

Also, it seems to be a good idea to insist that each node has its own fact. In your example 92 needs a fact!

So given all these precautions one can write, using DCGs:

node(3, nil, 14).
node(14, nil, 15).
node(15, nil, 92).
node(92, nil, nil).    % added!

inorder(I, Xs) :-
   phrase(inorder(I), Xs).

inorder(nil) -->
   [].
inorder(I) -->
   {dif(I, nil)},
   {node(I, L, R)},
   inorder(L),
   [I],
   inorder(R).

?- inorder(3,L).
   L = [3,14,15,92]
;  false.

The check your database for orphaned nodes:

orphan(Nr) :-
   node(_, L, R),
   ( Nr = L ; Nr = R ),
   dif(Nr, nil),
   \+ node(Nr, _, _).

So orphan(N) should fail on your database.

To get rid of the leftover choicepoint ; false. add the following rule in front of inorder//1:

inorder(Nil) --> {Nil == nil}, !.