Balanced Binary Tree

The height of a binary tree is the number of nodes on its longest path from the root down to a leaf, and an empty tree has height 0. A tree is height-balanced when, at every node, the heights of the node's left and right subtrees differ by at most 1.

Write is_balanced(root) that returns True if the tree is height-balanced and False otherwise. An empty tree is balanced.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4

is_balanced(build([3, 9, 20, None, None, 15, 7]))  # returns True
is_balanced(build([1, 2, 2, 3, 3, None, None, 4, 4]))  # returns False
is_balanced(build([]))  # returns True

The drawing shows the second tree. Its root's left subtree has height 3 and its right subtree has height 1, a difference of 2.

Constraints

• 0 to 5,000 nodes, at most 500 levels deep.