Check If Binary Tree Is Balanced

Method : Recursion. To determine a binary tree is balanced or not, we need to check the left subtree is balanced and right subtree is balanced, and the difference of hight of left subtree and right subtree should not be larger than 1.

Code:

public class Solution {
  public boolean isBalanced(TreeNode root) {
    // Write your solution here.
    if (root == null) {
      return true;
    }

    int left = getHeight(root.left);
    int right = getHeight(root.right);

    if (Math.abs(left - right) <= 1) {
      return isBalanced(root.left) && isBalanced(root.right);
    }
    return false;
  }

  private int getHeight(TreeNode root) {
    if (root == null) {
      return 0;
    }
    int left = getHeight(root.left);
    int right = getHeight(root.right);

    return Math.max(left, right) + 1;
  }
}

Time:worst case is finally it determined as balanced binary tree, so there are log(n) levels, and for each level, time complexity is O(n), so total is O(nlogn).