Find binary search trees based on traversal in prolog

Question

I am trying to write a Prolog predicate that gives a possible binary search tree for a given traversal. I chose to represent the tree like t(Root, Left Subtree, Right Subtree), leaves are simply t(Number) and when a subtree does not exist its value is nil.

This is what I have so far (only for postorder traversal in this case):

post(nil, []).
post(t(X), [X]).
post(t(N, L, R), T) :-
    post(L, TL), post(R, TR),
    append([TL, TR, [N]], T).

This works nicely in one way, but hangs in the other direction:

?- post(t(8, t(5, t(2), nil), t(12, t(9), t(16))), Trav).
Trav = [2, 5, 9, 16, 12, 8].

?- post(Tree, [2, 5, 9, 16, 12, 8]).
Tree = t(8, nil, t(12, nil, t(16, nil, t(9, nil, t(5, nil, t(2)))))) ;
Tree = t(8, nil, t(12, nil, t(16, nil, t(9, nil, t(5, nil, t(2, nil, nil)))))) ;
[execution hangs here]

I realized that post does not require a binary search tree, ie there is no requirement for all nodes in the left subtree to be less than the root node and all nodes in the right subtree to be greater than the root node, so I also wrote this:

tree(t(_)).
tree(nil).
tree(t(N, L, R)) :-
    tree(L), tree(R),
    ( L = t(NL, _, _) -> NL < N ; true ),
    ( R = t(NR, _, _) -> NR > N ; true ).

I thought I could just do ?- post(Tree, [...]), tree(Tree). to make Prolog only return actual binary search trees. However, I seem to be stuck already at generating possible trees.

How could I improve my code? Is this even doable?

Your data structure is unorthodox. Usually you have either nil or t(Value, Left, Right), and then a leaf node is t(Value, nil, nil). — TA_intern
So you are traversing a binary search tree but the list is not sorted because you are doing it post-order instead of in-order. Is that right? What exactly are you doing? — TA_intern
This chapter in a textbook has some answers and code for you: metalevel.at/prolog/dcg — TA_intern

jnmonette jnmonette · Accepted Answer · 2021-01-03T19:12:14

My suggestion is to write different code for different directions. Here is the code to transform a list back into a tree. The main difference with the original code is that we deconstruct the list (with last/3 and append/3) before reconstructing the tree. Note that I added the code to check for a search tree in third clause (the two maplist/2calls) but those can be as well removed if you want to keep it separately.

postlist_to_tree([],nil).
postlist_to_tree([X],t(X)).
postlist_to_tree(Xs,t(Last,LT,RT)):-
    last(Fore,Last,Xs),
    append(LL,RL,Fore),
    maplist('>='(Last),LL),
    maplist('=<'(Last),RL),
    postlist_to_tree(LL, LT),
    postlist_to_tree(RL, RT).

Now to have it as a single predicate, I would suggest to do something like this, using a non-logical predicate (ground/1 in this example) to decide which version to call depending on the instantiation of the arguments at call time.

post2(Tree,List):-
    ground(List),
    !,
    postlist_to_tree(List,Tree).
post2(Tree,List):-
    post(Tree,List).

Find binary search trees based on traversal in prolog

1 Answers