Symmetric Binary Tree

You are given a binary tree serialized in level-order (breadth-first order) where each node is represented by an integer and 'null' represents a missing node. Your task is to determine whether the given binary tree is symmetric. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Formally, a binary tree is symmetric if for every node, the following condition holds in \mathcal{O}(n) time:

\text{isSymmetric}(root) = True \iff \text{isMirror}(root, root)

where \text{isMirror}(tree1, tree2) is defined recursively as:

if tree1 is null and tree2 is null then return True
if tree1 is null or tree2 is null then return False
return (tree1.val == tree2.val) and isMirror(tree1.left, tree2.right) and isMirror(tree1.right, tree2.left)

Note that an empty tree is considered symmetric.

inputFormat

The input is given via stdin as a single line containing space-separated tokens representing the level order traversal of the binary tree. Each token is either an integer or the string null which represents an absent node.

outputFormat

Print True if the binary tree is symmetric; otherwise, print False. The output must be written to stdout.

1 2 2 3 4 4 3

True