CODEWITHSUNDEEP
prolog
user550413
user550413

Reputation: 4819

How to write a complete binary tree predicate using Prolog

What is the algorithm of checking if a Binary tree is a complete binary tree? (Using Prolog).

For example:

?- complete(nil).
true.

?- complete(tree(1,nil,nil)).
true.

?- complete(tree(1,tree(2,nil,nil),nil)).
false.

?- complete(tree(1,tree(2,nil,nil),tree(3,nil,nil))).
true.

Upvotes: 2

Views: 4160

Answers (1)

salva
salva

Reputation: 10244

complete(T) :- complete(T, _).

complete(nil, 0).
complete(tree(_, L, R), N) :-
  complete(L, N1),
  complete(R, N1),
  N is N1 + 1.

update:

It works for me:

?- complete(nil).
true.

?- complete(tree(1,nil,nil)).
true.

?- complete(tree(1,tree(2,nil,nil),nil)).
false.

?- complete(tree(1,tree(2,nil,nil),tree(3,nil,nil))).
true.

Upvotes: 3

Related Questions