Enumerating binary trees in Prolog

Question

I am trying to create Prolog rules to enumerate 'binary trees' in list form in Prolog. I am new to Prolog.

A tree with 0 nodes is an empty list:

[]

A tree with 1 node is:

[[],[]]

A tree with 2 nodes has 2 possibilities:

[[],[[],[]]]

[[[],[]],[]]

and so on.

Here are my rules:

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N,[Lc,Rc]) :-
  N > 1,
  bintree(N1,Lc),
  bintree(N2,Rc),
  N1 >= 0,
  N2 >= 0,
  N3 is N1+N2+1,
  N==N3.

Queries for 0 and 1 obviously work. For N=2, it prints one of the possibilities, but gives an error after I input the semicolon to get the other possibility. Queries for N>2 directly give an error. The error is always the same:

ERROR: >/2: Arguments are not sufficiently instantiated

I read about this error on some websites, but I can't figure out what is causing this error here.

Thanks for your help in advance.

To use an expression comparator in Prolog, all expressions must be fully instantiated (values known). You got the error because `N` had no value when you tried `N > 1`. What kind of query are you trying to satisfy? It's not at all clear in your question. — lurker, Mar 26 '15 at 11:29
It expects a pair. The first is a positive integer which is the number of nodes in the tree. The second is a tree in the format given that has that many number of nodes. Ex. bintree(2,A). should give A=[[],[[],[]]] ; A=[[[],[]],[]] which is the representation of the two binary trees with 2 nodes. It should terminate for all positive integers given as the first argument. — kpjoshi, Mar 26 '15 at 11:30
In your clause, the expressions `bintree(N1, Lc)` and `bintree(N2, Rc)` are being called with `N1` and `N2` uninstantiated variables. So the subsequenet `N > 1` will fail on that error message. — lurker, Mar 26 '15 at 11:45
I am trying to satisfy the type of query such as bintree(5,X). This will make prolog print the representation of a binary tree with 5 nodes. Each empty list [] is like a NULL pointer in C. A list with 2 elements [L,R] is a node which has the two elements L and R as children. When prompted with the semicolon, prolog should print all the possible trees for X having that many number of nodes, then print false. — kpjoshi, Mar 26 '15 at 12:00
@lurker Ok, I changed the order to the following: `bintree(N,[Cl,Cr]) :- integer(Nl), integer(Nr), Nl>=0, Nr>=0, Ns is Nl+Nr+1, N==Ns, bintree(Nl,Cl), bintree(Nr,Cr).` Now, I get false for all N>1. Basically I want it to try constructing left and right subtrees such that the sum of nodes in them, plus 1 (their parent) is equal to N. — kpjoshi, Mar 26 '15 at 12:04
English definition of my rules: Binary tree with 0 nodes: empty list. Empty list represents NULL pointer. Binary tree with 1 node : list containing 2 empty lists. Represents node with 2 NULL pointers as its children. [Cl,Cr] is a binary tree with N nodes if there exist non -ve integers Nl and Nr such that Nl+Nr+1=N and Cl is a binary tree with Nl nodes and Cr is a binary tree with Nr nodes. — kpjoshi, Mar 26 '15 at 12:15

lurker · Accepted Answer · 2015-03-29T17:02:19.673

Using the CLPFD library will help give a clean solution to generating the sizes. Then you don't need a wonky (;)) integer/1 predicate, which can be problematic:

:- use_module(library(clpfd)).

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N, [L, R]) :-
    N #> 1,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

Or simpler (thanks to @repeat's suggestion):

bintree(0,[]).
bintree(N, [L, R]) :-
    N #> 0,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

?- bintree(4, L).
L = [[], [[], [[], [[], []]]]] ;
L = [[], [[], [[[], []], []]]] ;
L = [[], [[[], []], [[], []]]] ;
L = [[], [[[], [[], []]], []]] ;
L = [[], [[[[], []], []], []]] ;
L = [[[], []], [[], [[], []]]] ;
L = [[[], []], [[[], []], []]] ;
L = [[[], [[], []]], [[], []]] ;
L = [[[], [[], [[], []]]], []] ;
L = [[[], [[[], []], []]], []] ;
L = [[[[], []], []], [[], []]] ;
L = [[[[], []], [[], []]], []] ;
L = [[[[], [[], []]], []], []] ;
L = [[[[[], []], []], []], []] ;
false.

?-

CLPFD is a nice, declarative way of expressing numeric constraints.

Thanks. Is this possible using only pure prolog, without this library? — kpjoshi, Mar 26 '15 at 14:17
This library *is* pure. Try for example GNU Prolog or B Prolog, where you do not have to import any library to use such an elementary feature as finite domain constraints. Great solution, +1! — mat, Mar 26 '15 at 15:22

score 0 · Answer 2 · answered Feb 16 '17 at 14:01

0

I know I posted this question a year ago, but I managed to solve it later without using any libraries. Here is my solution:

%binary tree generator
bintree(0,[]). %0 nodes - empty list
bintree(1,[[],[]]). %1 node - list containing 2 empty lists
bintree(N,[Cl,Cr]) :-
    N>=2, %check only if at least 2 nodes
    between(0,N,Nl), %let Nl be in [0,N]
    between(0,N,Nr), %similarly for Nr
    Ns is Nl+Nr+1, %total no. of nodes should add up correctly
    N==Ns, %so check for that
    bintree(Nl,Cl), %children should also be valid binary trees
    bintree(Nr,Cr).

answered Feb 16 '17 at 14:01

kpjoshi

111
8

1

That's a very bad "generator". For example, try the most general query: `?- bintree(N, Tree).` It yields two solutions, and then says: `ERROR: Arguments are not sufficiently instantiated`. I highly recommend you use CLP(FD) **constraints** to reason over integers, as in lurker's program. This will make your solution more general, usable in all directions as we expect from a relation. In your solution, both the wording ("check") and behaviour are very *imperative*, and your code only works in a very limited set of usage modes. As another example, try `?- bintree(N, [_,_]).`, and compare them! – mat Feb 16 '17 at 14:25

Enumerating binary trees in Prolog

2 Answers2