Checking if a tree is balanced or not

Question

I was writing this code to check if a tree is balanced or not and I ran into a situation where I would have liked the method to return 2 values at each step. First to signify whether the tree is balanced at that level or not, and second to return the height at the level so that I can use it to check the balanced nature of the parent. I ended up writing the method such that it returns -1 if the tree is not balanced and the actual height if the tree is balanced at that level.

Is there a better way to do it? If not, then I think I should at least have a better name for the method getHeight. Can you review my code as a whole and let me know my shortcomings?

public boolean isBalanced(Node root){
        return getHeight(root)!=-1;
    }

private int getHeight(Node node){
    if(node ==null)
        return 1;

    int leftHeight = getHeight(node.getLeft());
    int rightHeight = getHeight(node.getRight());
    if(leftHeight==-1 || rightHeight ==-1)
        return -1;

    int diff = Math.abs(leftHeight-rightHeight);
    if(diff>1)
        return -1;

    return Math.max(leftHeight,rightHeight) + 1;

}

Answer 1

These functions can be static, and therefore should be. Marking them static makes it clear that this is not object-oriented code. It also serves as a hint for the JIT to inline the helper function.

Instead of using Math.abs() and Math.max(), I suggest using Math.max() and Math.min(), which simplifies the conditionals a bit.

I would expect getHeight(null) to return 0. As you've written it, a node with no children is at height 2, which is a weird place to start counting, even if it works.

Never omit braces like that. You will contribute to a coding accident: [Citation 1] [Citation 2]. If you really want to omit braces, then put the entire conditional statement on the same line for safety.

private static int getHeight(Node node) {
    if (node == null) return 0;

    int leftHeight  = getHeight(node.getLeft()),
        rightHeight = getHeight(node.getRight());

    int taller  = Math.max(leftHeight, rightHeight),
        shorter = Math.min(leftHeight, rightHeight);

    if (shorter < 0 || taller - shorter > 1) {
        return -1;           // Unbalanced tree
    } else {
        return taller + 1;
    }
}

Answer 2

If you dont reuse the getHeight(Node node) method for calculating the height, yes, you should rename it as it does not return the height for unbalanced tree and therefore the behaviour is unexpected. I would rename it to getBalancedHeight(Node node) for example.

After renaming you can even make the method public - it reports the state of the tree - its balanced height.

As was suggested by 200_success, fore node == null you should return 0 as height, as it makes more sense.

Otherwise the code looks good.