Balanced Binary Tree

Problem

A binary tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one. Given the root of a binary tree, return True if it is height-balanced and False otherwise. An empty tree counts as balanced.

• The tree has at most 20,000 nodes and may be empty.
• Node values are integers and play no part in the answer.

Examples

• root = [8, 4, 12, 2, None, None, 15] → True. Both of the root's subtrees have height 2, and each of 4 and 12 has one child versus none, a difference of exactly one.
• root = [5, 3, None, 2, None, 1] → False. A left-leaning chain: at the root the left subtree has height 3 and the right is empty.
• root = [] → True.

Hints

1. The definition suggests computing the height at every node and comparing. What does that cost if you compute heights from scratch each time?
2. When you compute a subtree's height bottom-up, you already know both child heights. Can the height calculation also report "already unbalanced"?
3. Post-order DFS that returns the height, using a sentinel value such as -1 to mean "unbalanced somewhere below"; propagate the sentinel upward immediately.