Question4_1.java

/**
 * Implement a function to check if a binary tree is balanced.
 * For the purposes of this question, a balanced tree is defined to be a tree
 * such that the heights of the two subtrees of any node never differ by more than one.
 * 
 * Time  Complexity: O(n) (n is the number of nodes)
 * Space Complexity: O(h) (h is the height of tree)
 */

public class Question4_1 {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = height(node.left);
        if (leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = height(node.right);
        if (rightHeight == -1) {
            return -1;
        }
        
        if (Math.abs(rightHeight - leftHeight) <= 1) {
            return Math.max(rightHeight, leftHeight) + 1;
        } else {
            return -1;
        }
    }
    
    
    public static void main(String[] args) {
        Question4_1 question4_1 = new Question4_1();
        System.out.println(question4_1.isBalanced(null));
        TreeNode root = new TreeNode();
        System.out.println(question4_1.isBalanced(root));
        root.left = new TreeNode();
        System.out.println(question4_1.isBalanced(root));
        root.left.right = new TreeNode();
        System.out.println(question4_1.isBalanced(root));
        root.left.left = new TreeNode();
        System.out.println(question4_1.isBalanced(root));
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}