CODEWITHSUNDEEP
prologbinary-tree
angel ling
angel ling

Reputation: 5

How do I check is full binary tree?

How do I check full binary tree in prolog? I have the 2 base cases

1) if is empty tree, return yes

2) if is just root only, return yes

I'm stuck at the third one and I not sure what should I do with it. We only allow to use 1 arity: full(T). 

btree([]).
btree([H|T]):-btree(T).
btree([H|T]):-btree(H),btree(T).

full([]).
full([H]).
full([H|T]):-

anyone can guide me please. My idea is a tree does not have two nonempty tree then it is a full binary tree.

P/S: I am still new to stackoverflow. If I did ask something silly or improper way please do tell me. I want to learn how to use stackoverflow and also make sure of it in proper way.

Upvotes: 0

Views: 402

Answers (3)

user1812457
user1812457

Reputation:

Ok, since there is already an answer that doesn't answer the question at face value, here is mine. It doesn't add much anything to the answer by @lurker, it just offers details and explanations that were too much for comments. It also avoids CLP(FD) completely, which is why I felt it should be a separate answer.

You can start (as @lurker has) by using a more conventional binary tree representation. The empty tree is nil, and the non-empty tree is bt(Value, Left, Right) where Value is the value at this node and Left and Right are the left and right sub-trees. This is the conventional representation because it is at the very least more memory efficient. A "leaf" (a tree without sub-trees) is, in your original representation:

.(Value, .([], .([], [])))

instead of:

bt(Value, nil, nil)

The amount of memory needed to represent the two would be different between different Prolog implementations, but I don't know how to make the first smaller than the second.

Then: as @false commented above, a list is usually a collection of Things which conventionally has the following properties:

  • There can be no Things, or any number of Things in the collection;
  • The order of Things matters;
  • All the Things are somehow the same.

Using a list like you do breaks the last convention: the first argument is a value, while the second and third arguments are trees.

This doesn't exclude using list for representing a binary tree but it is unfamiliar.

With this out of the way: successor arithmetic is a silly way of doing actual arithmetic, but it is very convenient if you want to use pattern matching for non-negative integers. You cannot do it with the built-in integer type of Prolog, like 0 or -23 or whatever. Successor arithmetic gives you:

  • a zero which is structurally different from all positive integers: 0 vs s(_)
  • adding and subtracting is done by pattern matching, and both are done with the same operation: X + 1 is s(X).
  • negative numbers are not possible

So, you could define your "full tree" like this:

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

full_btree(nil, 0).
full_btree(bt(_, L, R), s(D)) :-
    full_btree(L, D),
    full_btree(R, D).

The s(D) and the two Ds state that the tree in your first argument is one deeper than the sub-trees, and that both sub-trees are the same depth. The empty tree nil has a depth of 0 (as defined in the first clause of full_btree/2).

This works as follows:

?- full_btree(nil).
true.

?- full_btree(bt(x, nil, nil)).
true.

?- full_btree(bt(x, bt(y, nil, nil), nil)).
false.

?- full_btree(bt(x, bt(y, nil, nil), bt(z, nil, nil))).
true.

?- full_btree(T), numbervars(T).
T = nil ;
T = bt(A, nil, nil) ;
T = bt(A, bt(B, nil, nil), bt(C, nil, nil)) ;
T = bt(A, bt(B, bt(C, nil, nil), bt(D, nil, nil)), bt(E, bt(F, nil, nil), bt(G, nil, nil))) . % and so on

One more thing: to close the circle, you can do successor arithmetic with lists, too. Just use [] instead of 0 and [_|X] for s(X). With this, you would have:

full_tree(nil, []).
full_tree(bt(_, L, R), [_|D]) :-
    full_tree(L, D),
    full_tree(R, D).

This is slightly less memory efficient, instead of s(s(s(0))) you would have .(_, .(_, ,(_, []))). However! it is now much easier to make actual integers out of the successor-notation integers, and the other way round: just use length/2. Writing a predicate that converts between s(s(...)) and an integer that works both ways in pure Prolog is not as trivial. I think it is possible to search Stackoverflow for such questions.

Upvotes: 2

lurker
lurker

Reputation: 58324

I would first probably choose a different representation for binary tree. In Prolog, it's generally more conventional and efficient to use a simple atom (such as nil) as a nil node, and something like btree(Value, Left, Right) as the tree term. Outside of that, the solution looks quite like what @pyon suggested.

% full_btree succeeds if `Tree` is a full binary tree

full_btree(Tree) :-
    full_btree(Tree, _).

full_btree(nil, 0).
full_btree(b(_, LeftTree, RightTree), Depth) :-
    Depth #> 0,
    SubDepth #= Depth - 1,
    full_btree(LeftTree, SubDepth),
    full_btree(RightTree, SubDepth).

The condition Depth #> 0 ensures, regardless of inputs, that the depth will not become negative, and thus helps ensure termination.

Upvotes: 3

isekaijin
isekaijin

Reputation: 19772

I'm going to assume that you represent trees as follows:

  • A leaf is an empty list.
  • A non-leaf node is a three-element list, whose last two elements are the subtrees.

Then:

helper([], 0).
helper([_,L,R], H) :- H #= G + 1, helper(L, G), helper(R, G).
/* Old version: helper([_,L,R], H) :- helper(L, G), helper(R, G), H is G + 1.
 * The improvement in the new version was suggested by lurker. Thanks!
 */

full(T) :- helper(T, _).

This works because full binary trees can be inductively defined as follows:

  • A leaf node is a full binary tree of height 0.
  • An non-leaf node whose children are both full binary trees of height G, is itself a full binary tree of height G + 1.

Upvotes: 2

Related Questions