Balanced Binary Tree

A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most 1.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree.

Output: true or false (an empty tree is balanced).

Constraints: 0 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: checking height() separately at every node is O(n²) on skewed trees. Instead return the height bottom-up and use -1 to mean "already unbalanced" — one O(n) pass.