prologbinary-tree

check if object is a binary tree in prolog


There is a task for prolog that sounds like this: write an istree predicate that returns true only if its argument is a binary tree. Example:

?- istree(t(a,t(b,nil,nil),nil)). Returns yes

?- istree(t(a,t(b,nil,nil))). Returns no

I tried to make my own code and stopped at this version:

domains
tree = nil; t(symbol, tree, tree).

predicates
istree(tree).
isleaf(tree).

clauses
istree(nil).
istree(t(_, Left, Right)) :-
istree(Left),
istree(Right).
isleaf(t(_, nil, nil)).

goal
%istree(t(a, t(b, nil, nil), nil)).
istree(t(a, t(b, nil, nil))).

Now, when I trying to enter the second line from the example (istree(t(a, t(b, nil, nil))).), I get an error: E;Test_Goal, pos: 246, 507 Type error: Wrong number of arguments

How can I fix it?


Solution

  • you need to define second argument "tree" as empty
    Here is example: istree(t(a, t(b, nil, nil), empty)).

    domains
    tree = nil; t(symbol, tree, tree); empty().
    
    predicates
    istree(tree).
    
    clauses
    istree(nil).
    istree(t(_, L, R)) :- istree(L), istree(R).
    
    goal
    istree(t(a, t(b, nil, nil), empty)).