Symmetric Tree

A binary tree is symmetric when it is a mirror image of itself around a vertical line through the root: the left half must match the right half flipped over, both in shape and in values. Write is_symmetric(root) that returns True if the tree is symmetric and False otherwise. An empty tree is symmetric.

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              1
    /   \           / \
   2     2         2   2
  / \   / \         \   \
 3   4 4   3         3   3

is_symmetric(build([1, 2, 2, 3, 4, 4, 3]))  # returns True
is_symmetric(build([1, 2, 2, None, 3, None, 3]))  # returns False
is_symmetric(build([5]))  # returns True

The drawings show the first two trees. In the second, both 3s are right children, so the right half is not the left half flipped over, even though each level reads the same both ways.

Constraints

• 0 to 5,000 nodes; values are integers.