Write a function to check whether a tree is balanced or not.

A balanced tree is one in which no two leaf nodes differ in distance from the root node by more than one.

Solution #1: The most straight forward approach would be to calculate the maximum and minimum depth of the tree and then find out their difference. Here is the code,

int maxDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}

int minDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);

    return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}

int isBalanced(node* root)
{
    if(maxDepth(root) - minDepth(root) > 1)
        return 0;
    else
        return 1;
}