Prolog binary search tree test - unwanted parents' parent node comparison

Question

I'm a Prolog rookie, please keep that in mind. I try to write a predicate to determine if some given term is a binary search tree. I figured out this code:

is_btree(nil).
is_btree(node(N,L,R)) :-
   number(N),
   is_btree(L), 
   is_btree(R), 
   small(N, R),
   big(N, L).

small(N, nil).
small(N, node(M,L,R)) :-
   N < M,
   small(N, L),
   small(N, R).

big(N, nil).
big(N, node(M,L,R)) :-
   N > M,
   big(N, L),
   big(N, R).

It works quite fine until I test a graph that has a node on the right side which passes the condition "higher than parent node", but it is higher or equal to parent node of the parent node. In this case Prolog reports failure.

Here is a sample query which fails unexpectedly:

?- is_btree(node(9,node( 3,node( 2,nil,nil),
                           node(10,nil,nil)),
                   node(12,node( 8,nil,nil),
                           node(15,nil,nil)))).
false.

A very similar problem arises when some node on the left side is higher than parent node of the parent node—a situation that is shown in the following illustration:

How can I check node values only with the value of their immediate parent node, but not the values of parents' parents?

but it should fail. that tree is an invalid BST and your predicate tests for *valid* BSTs. — Will Ness, Jan 08 '16 at 00:13
Shall we use explicit interval arithmetic? (Ab-)using FD domains appeared to be an option too, but *that* is too hackish for my taste. Using **2** FD variables (Alpha, Omega) for intervals seems more promising... — repeat, Jan 08 '16 at 00:49
@repeat I'm going to stick with the simple stuff in my answer. :) — Will Ness, Jan 08 '16 at 00:51

score 3 · Answer 1 · answered Jan 09 '16 at 21:03

Here's a slightly different take on the problem you want to solve.

dcg for collecting elements: in-order tree-traversal

in_order(nil) --> [].
in_order(node(X,L,R)) --> in_order(L), [X], in_order(R).

clpfd for relating adjacent list elements (which are all finite-domain variables)
```
chain(Zs, #<)
```

Let's put it all together and define is_bintreeFD/1 like this:

:- use_module(library(clpfd)).

is_bintreeFD(T) :-
   phrase(in_order(T), Zs),
   chain(Zs, #<).

Sample queries:

?- is_bintreeFD(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                       node(12,node(8,nil,nil),node(15,nil,nil)))).
false.

?- is_bintreeFD(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                       node(12,node(10,nil,nil),node(15,nil,nil)))).
true.

nice! is it possible to switch the two goals, so the traversal is stopped as soon as possible on failure? to have `chain` before the `phrase`? — Will Ness, Jan 10 '16 at 00:55

score 3 · Answer 2 · edited May 23 '17 at 12:33

This answer directly follows up on this previous answer, particularly on a comment by @WillNess that suggested "[...] switch the two goals, so the traversal is stopped as soon as possible on failure [...] to have chain before the phrase [...]".

lazy_chain/2 is like chain/2, but utilizes prolog-coroutining to wait for sufficient instantiation:

:- use_module(library(clpfd)).

lazy_chain(Zs, R_2) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> freeze(Zs, lazy_chain_aux(Zs,R_2))
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

lazy_chain_aux([], _).
lazy_chain_aux([Z0|Zs], R_2) :-
   freeze(Zs, lazy_chain_aux_(Zs,R_2,Z0)).

lazy_chain_aux_([], _, _).
lazy_chain_aux_([Z1|Zs], R_2, Z0) :-
   call(R_2, Z0, Z1),
   freeze(Zs, lazy_chain_aux_(Zs,R_2,Z1)).

Based on lazy_chain/2 we define is_bintreeL/2 like this:

is_bintreeL(T) :-
   lazy_chain(Zs, #<),
   phrase(in_order(T), Zs).

So... what about "early failure"?

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((phrase(in_order(T),Zs),eager_chain(Zs,#<))).
% 210 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4100201 Lips)
false.

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((lazy_chain(Zs,#<),phrase(in_order(T),Zs))).
% 52 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1225664 Lips)
false.

Laziness wins—at least in above case:)

Note, however, that using lazy_chain/2 with dcg can lead to bugs that are hard to find!

For a more robust solution, see this alternative answer...

For the sake of completeness, here's the source code of eager_chain/2:

eager_chain(Zs, R_2) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> eager_chain_aux(Zs, R_2)
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

eager_chain_aux([], _).
eager_chain_aux([Z0|Zs], R_2) :-
   eager_chain_aux_(Zs, R_2, Z0).

eager_chain_aux_([], _, _).
eager_chain_aux_([Z1|Zs], R_2, Z0) :-
   call(R_2, Z0, Z1),
   eager_chain_aux_(Zs, R_2, Z1).

score 2 · Answer 3 · edited May 23 '17 at 12:01

In this answer we use clpfd for declarative integer arithmetics.

:- use_module(library(clpfd)).

:- asserta(clpfd:full_answer).

We define the predicates is_bintree/1 and bintree_in/2 like this:

is_bintree(T) :-
   bintree_in(T, _).

bintree_in(nil, LB-UB) :-            % LB-UB denotes the open interval (LB,UB)
   LB #< UB.                         % that is all integers I suchthat LB<I<UB
bintree_in(node(Mid,L,R), LB-UB) :-
   Mid #> LB,
   Mid #< UB,
   bintree_in(L, LB-Mid),
   bintree_in(R, Mid-UB).

First, we test^1,2 the tree given by the OP:

| ?- bintree_in(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                       node(12,node(8,nil,nil),node(15,nil,nil))), _).
no

Let's fix the tree and check again!

| ?- bintree_in(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                       node(12,node(10,nil,nil),node(15,nil,nil))), _).
_A in inf..1, _B in 16..sup ? ;      % (somewhat sloppy)
no

OK! Next up are a few corner cases:

| ?- bintree_in(T, 0-0).             % no solution (as expected)
no
| ?- bintree_in(T, 0-1).             % empty tree
T = nil ? ;
no
| ?- bintree_in(T, 0-2).             % singleton tree
T = nil ? ;
T = node(1,nil,nil) ? ;
no

Note that while is_btree/1 can only "test", bintree_in/2 can both³ "test" and "generate"!

So let's generate (all possible) binary trees of a certain size in a small domain:

| ?- bintree_in(T, 0-3).             % T has less than 3 elements
T = nil ? ;
T = node(_A,nil,nil), _A in 1..2 ? ;
T = node(1,nil,node(2,nil,nil)) ? ;
T = node(2,node(1,nil,nil),nil) ? ;
no

| ?- bintree_in(T, 0-4).             % T has less than 4 elements
T = nil ? ;
T = node(_A,nil,nil), _A in 1..3 ? ;
T = node(_A,nil,node(_B,nil,nil)), _A#=<_B+ -1, _B#>=_A+1, _B in 2..3, _A in 1..2 ? ;
T = node(1,nil,node(2,nil,node(3,nil,nil))) ? ;
T = node(1,nil,node(3,node(2,nil,nil),nil)) ? ;
T = node(_A,node(_B,nil,nil),nil), _A#>=_B+1, _A in 2..3, _B in 1..2 ? ;
T = node(2,node(1,nil,nil),node(3,nil,nil)) ? ; 
T = node(3,node(1,nil,node(2,nil,nil)),nil) ? ;
T = node(3,node(2,node(1,nil,nil),nil),nil) ? ;
no

Last, we generate candidate solutions with bintree_in/2 and test these with is_btree/1!

is_btree/1 needs sufficient instantiation; labeling/2 provides us with ground terms.

| ?- call_time((  UB in 2..12, 
                  indomain(UB),
                  bintree_in(T, 0-UB),
                  term_variables(T, Zs),
                  labeling([], Zs),
                  \+ is_btree(T)
               ;  true
               ),
               T_ms).
T_ms = 6270 ? ;
no

^{Footnote 1:
The code in this answer runs (at on sicstus-prolog and swi-prolog.

Footnote 2:
All prolog-toplevel output presented is that of
SICStus Prolog 4.3.2 (64-bit).

Footnote 3:
Not just do both, but
(almost) arbitrarily mix generate and test, as it can handle partially instantiated terms.}

Wow, thanks for solutions, but i really just thought that this type of tree can be also valid... :D sorry guys — user3533469, Jan 08 '16 at 11:17

score 2 · Answer 4 · edited May 23 '17 at 12:24

In a comment to this previous answer, @WillNess suggested adding "early-failure" as a feature.

in_order_inf_sup//3 effectively combines in_order//1 and chain/2:

:- use_module(library(clpfd)).

in_order_inf_sup(nil, P, P) --> [].
in_order_inf_sup(node(X,L,R), P0, P) -->
   in_order_inf_sup(L, P0, P1),
   [X],
   { P1 #< X },
   in_order_inf_sup(R, X, P).

Sample queries (same as in previous answer):

?- phrase(in_order_inf_sup(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                                  node(12,node(8,nil,nil),node(15,nil,nil))),_,_),
          Zs).
false.

?- phrase(in_order_inf_sup(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                                  node(12,node(10,nil,nil),node(15,nil,nil))),_,_),
          Zs).
Zs = [2,3,8,9,10,12,15].

Will Ness · Answer 5 · 2016-01-08T23:09:56.463

But it should fail. That tree is an invalid BST and your predicate tests for valid BSTs.

There is something to be done here though. Right now you perform two passes over a tree - first in is_btree, second, with small/big.

The two can be fused into one, but an immediately apparent solution will do exactly what you want, and thus succeed on such invalid BSTs:

is_bst(nil).

is_bst(node(N,L,R)):- 
   (  L = nil 
   ;  L = node(M,LL,LR), M < N, is_bst(L), ....
   ),
   (  R = nil
   ;  ...... 
   ).

To fix it, we have to return one more result from the tree traversal — that is the tree's rightmost element — and use it in the comparisons for validation.

(edit: missed that the leftmost element also needs to be returned)

Prolog binary search tree test - unwanted parents' parent node comparison

5 Answers5

Linked