3.7 Balanced Binary Tree

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.

Logical Steps

1. Base case: at leaves, return current max depth, and assume current tree is true (if leave is false, than all trees will be false)
2. Before recursive calls, add max depth by 1 for current level
3. Divide
4. Decide balanced tree or not: left and right tree must be both balanced; max depth of both size must have a diff less than 1
5. Current max depth = the greater of left and right max depth

Code Template

class ReturnType {
    int maxDepth = 0;
    boolean isBalanced = true;

    ReturnType(int maxDepth, boolean isBalanced){
        this.maxDepth = maxDepth;
        this.isBalanced = isBalanced;
    }
}

public ReturnType helper(TreeNode root, int maxDepth) {
    // base case
    if (root == null)
        // when at leaf, return max depth of leave, and 
        // assume leaf is balanced tree
        return new ReturnType(maxDepth, true);

    // add max depth by 1, for current level, to feed into left and right
    maxDepth += 1;

    // divide
    ReturnType left = helper(root.left, maxDepth);
    ReturnType right = helper(root.right, maxDepth);

    /** conquer
    * if one of left & right tree is not balanced, current tree is not
    */
    boolean isBalanced = left.isBalanced && right.isBalanced;

    // if left & right max path diff greater than 1, not balanced tree
    if (Math.abs(left.maxDepth - right.maxDepth) > 1)
        isBalanced = false;

    // current max depth = max depth from left and right tree
    maxDepth = Math.max(left.maxDepth, right.maxDepth);

    return new ReturnType(maxDepth, isBalanced);
}

Common Mistakes

1. Mistake in deciding isBalanced:

    /** isBalanced is decided by conparing left and right 
    * max depth, not parent and child
    */
    if (left.maxDepth - depth > 1 || right.maxDapth - depth > 1)
        return false;
   

2. Mistake is base case at leave

    // base case
    if (root == null)
        // when at leave, should return current max depth
        // instead of 0 as max depth
        return new ReturnType(0, true);