In: Computer Science
Consider the following type of binary trees:
data Tree a = Leaf a | Node (Tree a) (Tree a)
A tree is balanced if the number of leaves in the left and right subtree of every node differ by at most one. Write a Haskell function balanced that returns whether a tree is balanced or not.
balanced :: Tree a -> Bool
Solution:
balanced:: Tree a-> Bool
int leftHeight //height of the left subtree
int rightHeight //height of the right subtree
if Tree a==NULL
return 1;
//calculating the height of the subtree
leftHeight = height(Tree->left);
rightHeight = height(Tree->right);
if( abs(leftHeight -rightHeight ) <= 1 &&
balanced(Tree->left) && balanced(Tree->right))
return 1;
return 0;
}
max:: a-> int, b-> int
{
return (a >= b)? a: b;
}
height:: Tree a-> int //function to calculate the height of the tree
{
if(Tree == NULL)
return 0;
else
return 1 + max(height(Tree->left), height(Tree->right));
}
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)