check whether binary tree is balanced or not?

Question

I was working on the problem of checking the height of the balanced binary tree and found one tutorial like

if (height of left subtree == -1)
return -1.

     public boolean isBalanced(TreeNode root) {
            if (root == null){
                return true;
            }
            return height(root) != -1;
            
        }

int height(TreeNode node){


`if (node  == null){`


return 0;
}


int left = height(node.left);


int right = height(node.right);


int bf = Math.abs(left- right);


if (bf \> 1 || left == -1 || right == -1){


return -1;


}


return Math.max(left,right)+1;


}

So, I was wondering in what case the height of the left subtree of the binary tree will be -1? Thank you

I looked over the tutorial and it was not explained properly.

Answer 1

Consider a tree. Which has a root and a child in left. Its child on left has only child on left and no right child and so on.

              R
             /
            C0
           /
          C1
         /
        C2
       /
      C3

Height is called with root R. Now Root R calls height on its left child C0 and right child (NULL). C0 does this to C1 then C1 does this same thing on C2 and so on.

So we'll calculate from C3 then to C2 then to C1, because that's how recursion is going to get executed.

In your function height(C3) now we call its height(C3->left) and height(C3->right). Both are NULL. Left and Right for them = 0. Height(C3) returns 1. As

(Math.max(left,right)+1; => Math.max(0,0)+1; => 1)

Now For function call height(C2)

left = Height(C2->left) i.e. C3
//hence left = 1;
right = Height(C2->right) i.e. NULL
//hence right = 0;

bf = Math.abs(left-right); => Math.abs(1-0); => 1

still all conditions are false and we return:

Math.max(left,right)+1; => Math.max(1,0)+1; => 2

Now let's come to height(C1)

left = height(C1->left) i.e. height(C2)
//left = 2
right = height(C1->right) i.e. height(NULL)
//right = 0

Now,

 bf = Math.abs(left-right); => bf = Math.abs(2-0); => bf = 2

since bf > 1 now, the if condition is executed and you return -1.

Now, for height(C0)

left = height(C0->left); => height(C1)
left = -1 //this is where you get height = -1

Now from this point above all your returns will be -1 because of the condition. Saying that this tree is not balanced.