Prolog, reconstruct BST trees from inorder list

Question

We well know inorder implementation for BST tree.

inorder(nil, []).
inorder(t(Root, L, R), List) :-
    inorder(L, ListLeft),
    inorder(R, ListRight),
    append(ListLeft, [Root|ListRight], List).

However, is it possible to do it for list ? I mean reconstruct all possible BST trees, for example:

inorder(X, [1,2,3]).
X = t(1, nil, t(2, nil, t(3, nil, nil))));
X = t(3, t(2, t(1, nil, nil), nil), nil), nil);
X = t(2, t(1, nil, nil), t(3, nil, nil));
false.

It seems to be impossible for me.

If you are serious about learning Prolog, you will have to learn about DCG (Definite Clause Grammar) eventually, so why not now. Take the time and read the [excellent primer](https://www.metalevel.at/prolog/dcg.html) written by Markus Triska. It has a lot of gold nuggets, including a solution to this question exactly. — , May 20 '16 at 12:19

score 4 · Accepted Answer · answered May 20 '16 at 12:03

4

First, let us use a Definite Clause Grammar (dcg) for relating trees to lists:

inorder(nil) --> [].
inorder(t(Root, L, R)) -->
    inorder(L),
    [Root],
    inorder(R).

The trick I will now apply is described in Ulrich Neumerkel's dissertation in Taming Left Recursion.

"... we add another state for the number of tokens that can be used by newly encountered nonterminals. The number of tokens that will be read by the terminals within a single rule are therefore reserved in advance."

In our case:

inorder(nil, Es, Es) --> [].
inorder(t(Root, L, R), [_|Es0], Es) -->
    inorder(L, Es0, Es1),
    [Root],
    inorder(R, Es1, Es).

Sample query (Ls omitted):

?- Ls = [1,2,3], phrase(inorder(Tree, Ls, _), Ls).
Tree = t(1, nil, t(2, nil, t(3, nil, nil))) ;
Tree = t(1, nil, t(3, t(2, nil, nil), nil)) ;
Tree = t(2, t(1, nil, nil), t(3, nil, nil)) ;
Tree = t(3, t(1, nil, t(2, nil, nil)), nil) ;
Tree = t(3, t(2, t(1, nil, nil), nil), nil) ;
false.

Another way to solve such issues is to use your Prolog system's tabling mechanism.

answered May 20 '16 at 12:03

mat

40,498
3
51
78

3

Please don't be modest and link the [DCG Primer](https://www.metalevel.at/prolog/dcg.html), which already has the solution for this verbatim. – May 20 '16 at 12:04
1

Thank you for the encouragement. I am however especially delighted by others linking to it and would prefer this way to spread the content. This also gives me confidence that it is indeed helpful and worth having around. – mat May 20 '16 at 12:06
1

Tell me please, `Es1` means rest of tokens remained by `inorder(L, Es0, Es1)`? Then we tell to `inorder(R, Es1, Es).`: You can use not more than `Es1` tokens. Rest of them return as `Es`. Yeah ? – May 21 '16 at 11:16
1

Yes, we use it this way, as a measure of the number of tokens that will be consumed if this rule applies. – mat May 21 '16 at 11:28

score 1 · Answer 2 · edited May 23 '17 at 10:29

If you like the trick I've proposed here, the only change required could be

:- use_module(carlo(snippets/when_)).

inorder(t(Root, L, R), List) -:- ...

and now

?- inorder(T,[1,2,3]).
T = t(1, nil, t(2, nil, t(3, nil, nil))) ;
T = t(1, nil, t(3, t(2, nil, nil), nil)) ;
T = t(2, t(1, nil, nil), t(3, nil, nil)) ;
T = t(3, t(1, nil, t(2, nil, nil)), nil) ;
T = t(3, t(2, t(1, nil, nil), nil), nil) ;
false.

Prolog, reconstruct BST trees from inorder list

2 Answers2

Linked