# 110. Balanced Binary Tree

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 | 3 |

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

:

1 | 1 |

## Analysis

**Methods:**

- 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)$

- Calculate heights first.
- 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.

- 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.
- 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 | public boolean isBalanced(TreeNode root) { |

### Pruning

**Note:** Return immediately if finding an unbalanced node.

1 | private boolean isBalancedPruning(TreeNode x) { |

### 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 | private static final int UNBALANCED = -2; // or -99 |

Comment