CODEWITHSUNDEEP
javabinary-tree
Stackimus Prime
Stackimus Prime

Reputation: 169

Checking if a Binary Tree is Balanced

I saw the question in a book (Cracking the Coding Interview). The suggested code is:

public boolean isBalanced(Node root) {

    if(root == null)
        return true;

    int leftHeight = getHeight(root.left);
    System.out.println("left height: " + leftHeight);
    int rightHeight = getHeight(root.right);
    System.out.println("right height: " + rightHeight);
    int diff = Math.abs(leftHeight - rightHeight);

    // check if difference in height is more than 1
    if (diff > 1)
        return false;

    // check if left and right subtrees are balanced
    else 
        return isBalanced(root.left) && isBalanced(root.right);

The part I don't understand is why do we need return isBalanced(root.left) && isBalanced(root.right). Isn't it enough just to check the height and return false if the hight is more than 1, and true otherwise?

Upvotes: 2

Views: 1113

Answers (1)

John Bupit
John Bupit

Reputation: 10618

No, it is not enough to just to check the height and return false if the height is more than 1, and true otherwise. Simply checking the root's height would result in false positives like the following:

        A
       / \
      B   F
     /   /
    C   G
   /   /
  D   H
 /   /
E   I

Upvotes: 6

Related Questions