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>
Advertisements

One thought on “Write a program to find whether a binary tree is a balanced ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s