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]:

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

## 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.

### Pruning

Note: Return immediately if finding an unbalanced node.

### 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.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.