Check if a binary tree is balanced

If difference between max depth and min depth of a tree is more than 1, then its not balanced. Finding min depth is very much same as max depth.

Solution 1: Find max depth and min depth and see if there difference is 1.

/* Finds the maximum depth of given tree */
int maxDepth (Tree node) {
    if (node == null) return 0;
    return 1 + max (maxDepth(node.left), maxDepth(node.right));
}

/* Finds the minimum depth of given tree */
int minDepth (Tree node) {
    if (node == null) return 0;
    return 1 + min (minDepth(node.left),  minDepth (node.right));
}

/* Finds if a given tree is balanced or not */
boolean isBalanced (Tree root) {
    return (maxDeth(root) - minDepth(root) <= 1);
}

Method 2: Since difference between max and min depth of balanced binary tree is 1, that means every leaf will either be at depth d or at depth d-1

We can then check depth at every node which has less than 2 children and if that is not one of d or d-1, then the tree is unbalanced.

However since we do not want to traverse the tree just to find the depth, we can store depth at each leaf in a set. At the end of traversal, if the set contains only two values and those differ by 1, then the tree is balanced.