Problem. A binary tree is height-balanced if, at every node, the heights of its left and right subtrees differ by at most 1. Return whether the tree is balanced.
3 1
/ \ / \
9 20 True 2 2 False (at the root:
/ \ / \ heights 3 and 1)
15 7 3 3
/ \
4 4
The condition is checked at every node, not just the root: a tree can have equal heights at the root and still be lopsided inside.
Why it matters. Balance keeps the height at O(log n), and the height is the cost of every operation on a search tree (lessons 10.9 and 10.10), the depth of every recursion over the tree, and the number of comparisons in a k-d tree query. An unbalanced binary search tree built from sorted inserts degrades into a linked list: O(n) per lookup. ML context: k-d trees for nearest-neighbour search are built balanced by splitting at medians (Change C); decision trees are often grown deep and unbalanced on purpose, which is why their depth is limited (lesson 10.2).