Write a program to find whether a binary tree is a balanced ?

As per wikipedia

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

A binary tree can be considered as balanced if

• The Left subtree is balanced
• The right subtree is balanced
• For a node the difference between height of left subtree and right subtree is not more than 1.

One approach to check balance condition for a node is by calculating height of left and right subtree and satisy the 3rd condition,then traverse down the tree to check for each child and keep continuing till you reach the leaf node. If condition is not satisfied for a node return false;

public class IsTreeBalance {


public boolean isBalance(TreeNode root){


if(root == null)

return true;

if (Math.abs(height(root.left)-height(root.right)) >1)

return false;

return isBalance(root.left) && isBalance(root.right);



}

  public int height(TreeNode node){


    if (node == null)

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

  }
}

So far so good. But the problem with this approach is that we visit each node (except root) more than once and hence not the best approach doing top-down check.

Opposite of top-down is bottom-up which is more efficient in this case. We start with leaf node and traverse up the tree. This way a node is visited only once.

public int isBalance1(TreeNode root){

if(root == null)

return 0;

int leftHeight = isBalance1(root.left);

int rightHeight = isBalance1(root.right);

if(Math.abs(leftHeight- rightHeight) > 1)

return -1;

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

 

}
<pre>