Using a static variable to break out of recursion

Question

Aim: Find if a tree is a balanced binary tree.

I have implemented a program that does work, but wanted to make it more efficient by preventing unnecessary recursion. To do this I am using a static variable, that is set when even a single condition is evaluated to false, so that every other recursive call returns, before making any of their own recursive calls.

static int shouldIExit=0;
public boolean isBalanced(TreeNode root) {
    if(root==null){
        return true;
    }
    if(shouldIExit==1 || Math.abs(height(root.left)-height(root.right))>1){
        height(root.right))>1: "+ (Math.abs(height(root.left)-height(root.right))>1) ) ;
        shouldIExit=1;
        return false;
    }
    else{
     return (isBalanced(root.left) && isBalanced(root.right) );   
    }
}

The problem is that the static variable is somehow being set even when no condition causes it to do so. i.e., shouldIExit is set to 1 even when the if condition corresponding to it, does not evaluate to true.

Is this me not understanding how static variables work?

Answer 1

You don't need a static variable. It's usually bad practice to use non-local variables (either static or instance variables) in a recursive method.

public boolean isBalanced(TreeNode root) {
    if(root==null) {
        return true;
    }
    if(Math.abs(height(root.left)-height(root.right))>1) {
        return false;
    } else{
     return (isBalanced(root.left) && isBalanced(root.right) );
    }
}

You could save some work if you combine the logic of height and isBalanced. I believe something like this should work:

public boolean isBalanced (TreeNode root) {
    return balancedHeight(root) >= 0;
}

public int balancedHeight (TreeNode root) {
    if (root == null) {
        return 0; // an empty tree is balanced
    }
    int left = balancedHeight(root.left);
    if (left < 0) {
        return -1; // left sub-tree is not balanced, so entire tree is not balanced
    }
    int right = balancedHeight(root.right);
    if (left == right) { // the tree is balanced if both sub-trees are balanced 
                         // and both have same height
        return left + 1;
    } else {
        return -1; // tree is not balanced - either the right sub-tree is not
                   // balanced or the two sub-trees have different heights
    }
}