Question

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

Answer 1

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. :)