#ctci

BalanceCheck.java

// according to the question, a tree is balanced if and only if:
// 1. the left and right substrees are both balanced
// 2. the height difference between left and right are no greater than 1
// a natural recursion approach should be fine. but we do have to return two things together (isBalanced and height)
// so we can create a private wrapper class to do that. Or we can just return -1 as height if not balanced.

// Assume we have the following binary tree node
// public class BTNode{
//     BTNode left;
//     BTNode right;
// }

public class BalanceCheck{
    public boolean isBalanced(BTNode root){
        return isBalancedTree(BTNode root) > 0;
    }
    
    private int isBalancedTree(BTNode root){
        if(root == null){
            return 0;
        }
        
        int leftRes = isBalancedTree(root.left);
        int rightRes = isBalancedTree(root.right);
        
        if(leftRes < 0 || rightRes < 0) return -1;
        
        // both subtrees are balanced, now we check the height difference
        int diff = leftRes > rightRes ? (leftRes - rightRes) : (rightRes - leftRes);
        if(diff > 1) return -1;
        
        return leftRes > rightRes ? (leftRes + 1) : (rightRes + 1);
    }
}

1. Good job!