CODEWITHSUNDEEP
prologbinary-tree
Alejandro Valdes
Alejandro Valdes

Reputation: 55

Prolog to count all the leaf nodes in a binary tree

I need to count all the internal nodes of a binary tree using prolog I can count all of the nodes using the following code

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.
internal(nil, 0).

And I thought that by changing the base case to 

internal(tree(_,nil, nil), 0).

I could get it to work but it returns false.

here is a test case that should return 4 internal(tree(8,tree(5,tree(2,nil,nil),tree(7,nil,nil)), tree(9,nil,tree(15,tree(11,nil,nil),nil))),I).

Could anyone tell me where my mistake is? Thanks

After reading your suggestions I've got this but it still fails.

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3. 
internal(tree(_,nil, R), I):- !, internal(R, I3), I is I3 + 1. 
internal(tree(_,L, nil), I):- !, internal(L, I3), I is I3 + 1.
internal(tree(_,nil, nil), 0).
internal(nil, 0).

Upvotes: 2

Views: 1784

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476614

If you change the predicate to:

internal(tree(_,nil, nil), 0).
internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.

then this will fail for trees with a nil child and a non-nil child this will fail.

Indeed: if the tree is tree(1, nil, tree(2, nil, nil)), then Prolog will first try to satisfy the base case, but sine nil is not equal to a tree(_, nil, nil), that fails. Next it aims to satisfy the recursive case, and first unifies L = nil, and R = tree(2, nil, nil). Now it calls internal(L, I2), but since internal(nil, I1) can not be satisfied it fails.

We can thus first construct a predicate that satisfies if the two subtrees result in an internal node:

isinternal(tree(_, _, _), _).
isinternal(_, tree(_, _, _)).

so this predicate succeeds if at least one of the subtrees is a tree(_, _, _).. Now we can use this predicate to count the number of internal nodes:

internal(nil, 0).
internal(tree(_, nil, nil), 0).
internal(tree(_, L, R), I) :-
    isinternal(L, R),
    internal(L, NL),
    internal(R, NR),
    I is NL + NR + 1.

The above can be improved in terms of readability. I leave this as an exercise.

Upvotes: 1

Related Questions