Reading material

Additional material

The following method tests if a strong binary tree is balanced.
public static boolean isBalanced(BinaryTree tree) {
    if (tree.isEmpty()) {
        return true;
    } else {
        return isBalanced(tree, tree.root());
    }
}

private static boolean isBalanced(BinaryTree tree, Position position) {
    if (tree.isExternal(position)) {
        return true;
    } else {
        Position left = tree.leftChild(position);
        Position right = tree.rightChild(position);
        if (Math.abs(size(tree, left) - size(tree, right)) <= 1) {
            return (isBalanced(tree, left) && isBalanced(tree, right));
        } else {
            return false;
        }
    }
} 
However, we still have to deal with the exceptions which may be thrown by the BinaryTree methods root, isExternal, leftChild and rightChild (the compiler cannot check that these methods do never throw exceptions in the abobe methods). The exceptions can be handled in two ways. They can be specified.
public static boolean isBalanced(BinaryTree tree) throws TreeException {
    if (tree.isEmpty()) {
        return true;
    } else {
        return isBalanced(tree, tree.root());
    }
}

private static boolean isBalanced(BinaryTree tree, Position position) throws TreeException {
    if (tree.isExternal(position)) {
        return true;
    } else {
        Position left = tree.leftChild(position);
        Position right = tree.rightChild(position);
        if (Math.abs(size(tree, left) - size(tree, right)) <= 1) {
            return (isBalanced(tree, left) && isBalanced(tree, right));
        } else {
            return false;
        }
    }
} 
Or they can be caught.
public static boolean isBalanced(BinaryTree tree) {
    try {
        if (tree.isEmpty()) {
            return true;
        } else {
            return isBalanced(tree, tree.root());
        }
    } 

    /* 
     * root never throws an exception but the compiler cannot 
     * check this.
     */
    catch (TreeException e) {

        /* 
         * Since this method always has to return a value of type boolean
         * we return false in this case.
         */
        return false;
    }
}

private static boolean isBalanced1(BinaryTree tree, Position position) {
    try {
        if (tree.isExternal(position)) {
            return true;
        } else {
            Position left = tree.leftChild(position);
            Position right = tree.rightChild(position);
            if (Math.abs(size(tree, left) - size(tree, right)) <= 1) {
                return (isBalanced1(tree, left) && isBalanced1(tree, right));
            } else {
                return false;
            }
        }
    } 
        
    /* 
     * isExternal, leftChild and rightChild never throw an exception
     * but the compiler cannot check this.
     */
    catch (TreeException e) {

        /*
         * Since this method always has to return a value of type boolean
         * we return false in this case.
         */
        return false;
    }
}

Note that the above methods only use methods of the interface BinaryTree (and not of the class LinkedBinaryTree).

If the above methods are placed in the class named C, then they can be used as follows.

/* Create the tree  1
 *                 / \
 *                2   3
 */
LinkedBinaryTree empty = new LinkedBinaryTree();
LinkedBinaryTree left = new LinkedBinaryTree(new Integer(2), empty, empty);
LinkedBinaryTree right = new LinkedBinaryTree(new Integer(3), empty, empty);
LinkedBinaryTree tree = new LinkedBinaryTree(new Integer(1), left, right);

/* Test if the tree is balanced */
System.out.print("The tree " + tree);
if (!C.isBalanced(tree)) { // tree is not balanced
    System.out.print(" not");
}
System.out.println(" balanced.");

The worst case running time of the above method is O(n2), where n is the number of nodes of the tree. There exits a method which computes the size of the tree and whether it is balanced "at the same time". The worst case running time of that method is O(n).