Check if Binary Tree is Height Balanced?

Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

The solution presented is a recursive. Find the height of left and right subtrees and check the difference of the heights. If the difference is more than 1 the tree is not balanced. The tree is balanced if the difference is zero or one.

Implementation:

public class CrazyforCode {
    public boolean isBalanced(TreeNode root) {
        int left,right;
        if(root ==null){ return true;}
        left = getHeight(root.left);
        right =getHeight(root.right);

        return (Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right));

    }

    public int getHeight(TreeNode root){
        if(root ==null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);

        return 1+ (left>right?left:right);
    }
}

2 Thoughts on “Check if Binary Tree is Height Balanced?

  1. Pankaj C. on April 18, 2016 at 12:36 pm said:

    Nice solution, but space complexity will be O(H) where H is the height of the tree. This is because stack allocation for recursion.

  2. Nimesh on June 28, 2016 at 9:51 pm said:

    Should we consider stack allocation of recursion for space complexity.we are not allocating any space right

Leave a Reply to Nimesh Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation