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;
}

Comment