110. Balanced Binary Tree

//O(nh) time and O(h) space
//In case of balanced trees h = logn whereas in case of skewed tree h = n
class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root);
    }
    public boolean helper(TreeNode root){
        if(root==null) return true;
        int left = height(root.left);
        int right = height(root.right);
        if(Math.abs(left-right)>1) return false;
        return helper(root.left)&&helper(root.right);
    }
    public int height(TreeNode node){
        if(node==null) return 0;
        return 1+Math.max(height(node.left), height(node.right));
    }
}

//O(n) time and O(n) space
class Solution {
    public boolean isBalanced(TreeNode root) {
        //Sanity Check
        if(root==null) return true;
        return (helper(root)!=-1);
    }
    public int helper(TreeNode root){
        if(root==null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if(left==-1 || right==-1) return -1;
        return (Math.abs(left-right)>1)?-1:1+Math.max(left,right);
    }
}