Check if a tree is a min heap

Question

How do I get a predicate in prolog to return a value?

I need to find a node of a tree and also check if its a min heap or not. I'm guessing it goes something like this:-

getnode(tree(_, node, _), node).

My code so far is this

minheap(tree(L, Node, empty)) :-
    getnode(L, Val),
    Node =< Val,
    minheap(L).
minheap(tree(empty, Node, R)) :-
    getnode(R, Val),
    Node =< Val,
    minheap(R).

getnode(tree(_,n,_)  , n).

Input is of the type-

minheap(tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))).

Output should be true.

Answer 1

In order to solve this, you better define some utility predicates that make life simpler.

For instance predicate lower/2. lower(Tree,Value) that succeeds if either Tree is empty, or the value of the Tree is higher than Value. So you can implement this like:

lower(empty,_).
lower(tree(_,TreeValue,_),Value) :-
    TreeValue >= Value.

Next we define the predicate minheap/1. An empty tree is definitely a minheap. Furthermore a tree is a minheap if its children are lower and all the children are minheap/1s themselves, so:

minheap(empty).
minheap(tree(Left,Value,Right)) :-
    lower(Left,Value),
    lower(Right,Value),
    minheap(Left),
    minheap(Right).

and that's it. This is better than trying to do all the work in the minheap/1 predicate since in that case you should handle five cases: empty, tree(empty,val,empty), tree(tree(..),val,empty), tree(empty,val,tree(..)) and tree(tree(..),val,tree(..)). By using the lower/2 helper predicate, we only have to handle two cases: empty and tree/3.