Symmetric Binary Tree

Problem Background

Special for beginners, ^_^

Problem Description

A binary tree is called symmetric if the structures of its left and right subtrees are mirror-symmetric — that is, either both subtrees are empty, or both are non-empty. Write a program to decide whether a given binary tree is symmetric.

Example: the binary tree $T_1$ in the figure below is symmetric, while $T_2$ is not.

The binary tree is given in level order; reading # means the corresponding node is empty. Tree $T_1$ = ABCDE, $T_2$ = ABCD#E. If the tree is symmetric, output Yes; otherwise output No.

Input Format

One string, describing the tree as above, with length less than $50$.

Output Format

Output Yes or No according to whether the tree is symmetric. These two words must be printed exactly as shown — the judge compares them character by character.

Sample Input

ABCDE

Sample Output

Yes

Constraints

Length of the string $< 50$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• Read the string into a level-order array (index $i$'s children are at $2i+1$ and $2i+2$). A # is an empty node.
• Recursively check: two subtrees are mirror-symmetric if their roots are both empty, or both non-empty and left-of-first matches right-of-second and right-of-first matches left-of-second.