How to write a complete binary tree predicate using Prolog

Question

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.

Well, I need all the leaves to be in the same distance from the root. So the most simple algorithm is going through all of them and check if all have the same distance from the root. — user550413
– user550413, Commented Jan 22, 2011 at 16:10
Perhaps a slightly quicker approach: Find the depth of one leaf, then look for a leaf node that has less depth or a non-leaf node that has an equal depth. If you find either of those, the binary tree is not "complete". — hardmath
– hardmath, Commented Jan 22, 2011 at 21:25

salva · Accepted Answer · 2011-01-23 06:41:12Z

3

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.

edited Jan 23, 2011 at 6:41

answered Jan 22, 2011 at 21:26

salva

10.3k4 gold badges31 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user550413 Over a year ago

It doesn't work. It returns true for all the examples I showed above. If I understood what you have tried to do is to check that the right sub-tree and left sub-tree has the same height which doesn't define a complete binary tree.

salva Over a year ago

@user550413: has you actually tried it? because it works with me, at least for the samples in your post!

Collectives™ on Stack Overflow

How to write a complete binary tree predicate using Prolog

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related