Reading material

pages 178-180.

Additional material

The following method tests if a binary tree is balanced.
/**
 * Tests if the specified binary tree is balanced.
 * @param tree the binary tree to be tested.
 * @return true if the specified binary tree is balanced, false otherwise.
 */
public static boolean isBalanced(BinaryTree tree) {
    if (tree.isEmpty()) {
        return true;
    } else {
        return isBalanced(tree, tree.root());
    }
}

/**
 * Tests if the subtree of the specified binary tree rooted at the specified 
 * node is balanced.
 * @param tree the binary tree to be tested.
 * @param node root of the subtree to be tested.
 * @return true if the subtree of the specified binary tree rooted at the 
 * specified node is balanced, false otherwise.
 */
private static boolean isBalanced(BinaryTree tree, Position node) {
    if (tree.isExternal(node)) {
        return true;
    } else {
        Position left = tree.leftChild(node);
        Position right = tree.rightChild(node);
        if (Math.abs(size(tree, left) - size(tree, right)) <= 1) {
            return (isBalanced(tree, left) && isBalanced(tree, right));
        } else {
            return false;
        }
    }
} 

/**
 * Returns the size of the subtree of the specified binary tree rooted at 
 * the specified node.
 * @param tree the binary tree to be considered.
 * @param node root of the subtree the size of which is to be returned.
 * @return the size of the subtree of the specified binary tree rooted at 
 * the specified node.
 */
private static int size(BinaryTree tree, Position node) {
    if (tree.isExternal(node)) {
        return 1;
    } else {
        return 1 + size(tree, tree.leftChild(node)) + size(tree, tree.rightChild(node));
    }
} 
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 never throw exceptions in the above methods). The exceptions can be handled in two ways. They can be specified.
public static boolean isBalanced(BinaryTree tree) throws TreeEmptyException, InvalidPositionException {
    if (tree.isEmpty()) {
        return true;
    } else {
        return isBalanced(tree, tree.root());
    }
}

private static boolean isBalanced(BinaryTree tree, Position node) throws InvalidPositionException {
    if (tree.isExternal(node)) {
        return true;
    } else {
        Position left = tree.leftChild(node);
        Position right = tree.rightChild(node);
        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 (TreeEmptyException e) {

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

private static boolean isBalanced(BinaryTree tree, Position node) {
    try {
        if (tree.isExternal(node)) {
            return true;
        } else {
            Position left = tree.leftChild(node);
            Position right = tree.rightChild(node);
            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 (InvalidPositionException e) {

        /*
         * Since this method always has to return a value of type boolean
         * we return false in this case.
         */
        return false;
    }
}
The size method can be handled similarly.

BooleanAndInt.java

/**
 * Returns whether the specified binary tree is balanced and the size of
 * the specified tree.
 * @param tree the binary tree to be considered.
 * @return whether the specified binary tree is balanced and the size of
 * the specified tree.
 */
public static BooleanAndInt isBalancedAndSize(BinaryTree tree) {
    if (tree.isEmpty()) {
        return new BooleanAndInt(true, 0);
    } else {
        return isBalanced(tree, tree.root());
    }
}

/**
 * Returns whether the subtree of the specified binary tree rooted at the
 * specified node is balanced and the size of the subtree.
 * @param tree the binary tree to be considered. 
 * @param node the root of the subtree to be considered.
 * @return whether the subtree of the specified binary tree rooted at the
 * specified node is balanced and the size of the subtree.
 */
private static BooleanAndInt isBalancedAndSize(BinaryTree tree, Position node) {
    if (tree.isExternal(node)) {
        return new BooleanAndInt(true, 1);
    } else {
        BooleanAndInt left = isBalancedAndSize(tree, tree.leftChild(node));
        BooleanAndInt right = isBalancedAndSize(tree, tree.rightChild(node));
        boolean isBalanced = (Math.abs(left.getInt() - right.getInt()) <= 1) && // the root is balanced
                             left.getBoolean() &&                               // the internal nodes in the left subtree are balanced
                             right.getBoolean();                                // the internal nodes in the right subtree are balanced
        int size = 1 + left.getInt() + right.getInt();
        return new BooleanAndInt(isBalanced, size);
        }
    }
}