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
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
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
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

lurker lurker · Accepted Answer · 2015-03-26T12:51:51

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.

Enumerating binary trees in Prolog

2 Answers