Symmetric Binary Tree

Given a binary tree, determine if it is symmetric around its center (i.e. a mirror of itself).

The binary tree is represented in level-order, where missing nodes are denoted by the token null (without quotes). For example, the symmetric binary tree below:

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

is represented as:

1 2 2 3 4 4 3

While a non-symmetric tree may be represented as:

    1
   / \
  2   2
   \   \
   3   3

represented by:

1 2 2 null 3 null 3

Note: An empty tree should be considered symmetric.

The underlying idea is to compare the left and right subtrees to check if they are mirror images of each other. In mathematical notation, for every node with left subtree L and right subtree R, we need to verify:

$$L.val = R.val \quad \text{and} \quad isMirror(L.left, R.right) \quad \text{and} \quad isMirror(L.right, R.left)$$

inputFormat

The input is given as a single line read from standard input. It contains the level-order traversal of the binary tree, with each token separated by a space. Each token is either an integer (representing a node's value) or the string null indicating a missing node.

Examples:

• 1 2 2 3 4 4 3
• 1 2 2 null 3 null 3
• null (represents an empty tree)

outputFormat

Output a single line to standard output: True if the tree is symmetric, or False otherwise.

## sample

1 2 2 3 4 4 3

True