1.1 Check if a Binary Tree is balanced

Input: TreeNode root

Output: boolean if the tree is balanced

Corner case: return true if the input is null

Solution 1:

1. To demonstrate, start with the solution to check that for each node, if the height difference b/w its left and right children is <= 1

2. Each node returns the value of its height to its parent

3. Subproblem: isB(root.left) && isB(root.right) && |leftHeight - rightHeight| <= 1, return true

4. Base case: when root hits null below leaf node

TC: n = # of nodes in the tree, traverse all node: n * each time call getHeight logn = O(nlogn)

SC: O(height of recursion tree), worst O(n), avg O(logn)

class TreeNode {
  public int key;
  public TreeNode left;
  public TreeNode right;
  public TreeNode (int key) {
    this.key = key;
  }
}

public class Solution {
  public boolean isBalanced(TreeNode root) {
    if (root == null) { return true; }
    boolean left = isBalanced(root.left);
    boolean right = isBalanced(root.right);
    if (!left || !right) { return false; }
    int lH = getHeight(root.left);
    int rH = getHeight(root.right);
    if (Math.abs(lH - rH) > 1) { return false;  }
    return true;
  }

  private int getHeight(TreeNode root) { 
    if (root == null) { return 0; }
    int lH = getHeight(root.left);
    int rH = getHeight(root.right);
    return Math.max(lH, rH) + 1 ;
  }
}

Solution 2: (not optimized)

1. Instead of calling getHeight each time traversing a node in the tree, return the value of the tree height if it's balanced, and a special value if it's not

2. What to expect from child trees?

left value >= 0, if -1, not balanced

right value >= 0, if -1, not balanced

3. What to do in the current layer?

Case 1: if either left or right child is balanced, return -1

Case 2: if both balanced, check if |lH - rH| <= 1

4. What to report to the parent?

if balanced, max(lH, rH) + 1, if not, -1

public int isBalanced(TreeNode root) {
  if (root == null) { return 0; }
  int lH = isBalanced(root.left);
  int rH = isBalanced(root.right);
  if (lH == -1 || rH == -1 || Math.abs(lH - rH) > 1) { return -1;}
  return Math.max(lH, rH) + 1;
}