Write Prolog rules as described in the questions below. You may use any Prolog b

Question

Write Prolog rules as described in the questions below. You may use any Prolog builtin predicates.

A binary tree is defined by the structure node(left,right), where left and right can be
either another node or any Prolog data item.

Write the rule isBalanced(Tree) that determines if the tree is balanced.
A binary tree is balanced if, at every node, the difference between the number of
leaves appearing in the left and right subtree is at most one. (A tree which contains
just one leaf is considered balanced.)
For example:
?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.

Explanation / Answer

cbal_tree(0, nil).
cbal_tree(N, t(x,L,R)) :-
    N > 0,
    N0 is N - 1,    % -1 to account for root node
    N1 is N0 mod 2,
    N2 is N0 - N1,

    permutation([N1,N2], [NLeft,NRight]),

    cbal_tree(NLeft, L),
    cbal_tree(NRight, R).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.