Is Binary Tree Balanced

Problem Statement

Given a binary tree, determine if it is height-balanced. For this problem, 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.

Approach

• Since, the difference in the depth of two subtrees rooted at each node should not be more than 1, we have to check the following conditions:
• If the root node is null, then the tree is balanced
• If the two subtrees rooted under the root are of different height then its not a height balanced binary tree. Return false
• If two subtrees rooted under the root are of same height then check recursively if each node (left child and right child) are balanced or not. Return true if they are balanced and false otherwise

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public boolean isBalanced(TreeNode root) {
        if(root == null){
                return true;
        }
        int height = 0;
        if(Math.abs(getHeight(root.left,height) - getHeight(root.right,height)) > 1){
            return false;
        }else if(isBalanced(root.left) && isBalanced(root.right)){
            return true;
        }else{
            return false;
        }
    }
    
    /** Return the height of the Binary tree given node and an initial height of 0*/
    private int getHeight(TreeNode node,int height){
        if(node == null){
            return height;
        }else{
            height++;
        }
        return Math.max(getHeight(node.left,height), getHeight(node.right,height));
    }
}