Write Prolog rules as described in the questions below. You may use any Prolog b
ID: 3903037 • Letter: W
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
A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced.
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.
To check if a tree is height-balanced, get the height of left and right subtrees. Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.
Following is the simple program to determine whether a binary tree is height balanced or not:
bool isBalanced(struct node *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);
if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.