Balanced binary tree
You get the root of a binary tree. A node's subtree is the node together with everything below it. The height of a subtree is the number of nodes on its longest downward path, and an empty subtree has height 0. A tree is balanced when, at every node, the subtrees of its left and right children differ in height by at most 1.
Return True if the tree is balanced and False if it is not. An empty tree is balanced.
Examples write a tree level by level, left to right, with None where a child is missing.
root = [1, 2, 3, 4]OutputTrueNode 2 has heights 1 and 0 below it. The root has heights 2 and 1. Every difference is at most 1.
root = [1, 2, 3, 4, None, None, 5, 6, None, None, 7]OutputFalseThe root looks fine: both of its subtrees have height 3. But node 2 has a left subtree of height 2 (nodes 4 and 6) and no right subtree, a difference of 2.
root = []OutputTrueAn empty tree has no node that breaks the rule.
0 ≤ number of nodes ≤ 4 × 105
The tree is at most 900 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.