Reference: LeetCode
Difficulty: Easy

Problem

Given a binary tree, determine if it is height-balanced. For this problem, 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.

Note:

Example:

Given the following tree [3,9,20,null,null,15,7]:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7  // true

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4  // false

Analysis

Methods:

  1. Brute-Force
    • Strictly according to the definition of balanced binary tree: The difference between the heights of the two subtrees is not greater than 1, and both subtrees are also balanced.
      • Calculate heights first.
        • Best: $O(\log{N})$ when the tree is balanced.
        • Worst: $O(N)$
      • Check if balanced. DFS every node. $O(N)$
    • It is kind of like preorder traversal. It does a lot of repeated work. Balance checking could be done during calculating the heights.
    • Time:
      • Best: $O(N\log{N})$ when the tree is balanced.
      • Worst: $O(N^2)$
    • Space:
      • Best: $O(\log{N})$ when the tree is balanced.
      • Worst: $O(N)$
    • Note: Might be improved by using a hash map to store the calculated heights. So we don’t need to do unnecessary height calculation.
  2. Optimization
    • Idea 1: Use postorder traversal. Prune unnecessary balance checking.
    • Idea 2: Do balance checking during height calculation.
      • Time: $O(N)$
      • Space: $O(\log{N})$ or $O(N)$

Code

Brute-Force

Note:

  • In the height function, when the node is null, it should return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isBalanced(TreeNode root) {
  return isBalancedHelper(root);
}

//  null    O      O      O
//                /      / \
//               O      O   O
//  true   true  true   true
private boolean isBalancedHelper(TreeNode x) {
  if (x == null) {
    return true;
  }
  // Calculate heights
  int diff = Math.abs(height(x.left) - height(x.right));
  // Check if balanced
  return (diff <= 1) && isBalancedHelper(x.left) && isBalancedHelper(x.right);
}

private int height(TreeNode x) {
  if (x == null) {
    return -1;
  }
  return Math.max(height(x.left), height(x.right)) + 1;
}

Pruning

Note: Return immediately if finding an unbalanced node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private boolean isBalancedPruning(TreeNode x) {
  if (x == null) { // base case
    return true;
  }
  
  // Return immediately if finding an unbalanced node
  if (!isBalancedPruning(x.left)) return false;
  if (!isBalancedPruning(x.right)) return false;
  
  int diff = Math.abs(height(x.left) - height(x.right));
  return (diff <= 1);
}

//  null     O      O    O
//                 /    / \
//                O    O   O
//   -1      0    1      1     <-- height  
private int height(TreeNode x) {
  if (x == null) return -1;
  return Math.max(height(x.left), height(x.right)) + 1;
}

All-In-One

Note:

  • Do everything in height calculation.
  • Most solutions in the discussion section use -1 as the unbalanced value. They assume that the height is defined by nodes instead of links. Both values are fine since what matters is the relative difference between nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private static final int UNBALANCED = -2; // or -99

// "-2" indicates that it is not balanced
public boolean isBalanced(TreeNode root) {
  return isBalancedHelper(root) != UNBALANCED;
}

//  null     O      O    O
//                 /    / \
//                O    O   O
//   -1      0    1      1     <-- height
private int isBalancedHelper(TreeNode x) {
  if (x == null) { // base case. balanced
    return UNBALANCED;
  }

  // return immediately
  int leftHt = isBalancedHelper(x.left);
  if (leftHt == UNBALANCED) return UNBALANCED;

  int rightHt = isBalancedHelper(x.right);
  if (rightHt == UNBALANCED) return UNBALANCED;

  if (Math.abs(leftHt - rightHt) > 1) return UNBALANCED;
  return Math.max(leftHt, rightHt) + 1;
}