dsa · easy
Balanced Binary Tree
A binary tree is **height-balanced** when, at **every** node, the heights of the two child subtrees differ by at most 1.
Arguments
root— binary tree as nested [val, left, right] or None
Height of a subtree is the number of nodes on the longest downward path from that subtree’s root to a leaf (0 for None, 1 for a leaf).
Each node is [val, left, right] or None. Return whether root is height-balanced.
Example
[3, [9, None, None], [20, [15, None, None], [7, None, None]]].
The left subtree of 3 is a leaf (height 1). The right subtree 20 has two leaves (height 2). |2 - 1| = 1, and every smaller node is a leaf or balanced, so the answer is true.
[1, [2, [3, [4, None, None], None], None], [5, None, None]] is false: the left spine is three edges deep while the right child of the root is a leaf, so the heights at the root differ by more than 1.
Constraints
Number of nodes in [0, 2000] -10^4 <= val <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [3, [9, None, None], [20, [15, None, None], [7, None, None]]] Expected: true
Example 2
Input: [1, [2, [3, [4, None, None], None], None], [5, None, None]] Expected: false