Prolog to count all the leaf nodes in a binary tree

Question

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).

Is your call here using l as result? l is not a variaable, but a constiers.so you should use uppercase v identifiers. — Willem Van Onsem
@WillemVanOnsem the call is using uppercase i as a result, not l, and as far as I understand the +1 is adding 1 to every node after a solution for the base cases has been found which would return 0 — Alejandro Valdes
But here you have a tree(_, nil, tree(_, _, _)) in your example. How does this matches the inductive, or base case if you removed internal(nil, 0)? — Willem Van Onsem
but if you have a tree(_, nil, tree(_, _, _)), then the left child is nil, and the right one a tree, so the basecase is not sufficient, nor is the inductive satisfying, since it will call internal/2 in the children, hence it will call internal(nil, I1). — Willem Van Onsem

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2018-10-26T19:51:45

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.

Prolog to count all the leaf nodes in a binary tree

1 Answers