Newton's Apple

Interview

Time limit1sMemory limit128 MB

Summary

Parse two binary trees from post-order tokens with nil markers, then decide whether one can be turned into the other by swapping left and right children at any nodes.

Level: Medium6 of 10
Topics: Tree, Recursion, DFS, Implementation
Solved: No attempts yet

Problem

Two binary trees $A$ and $B$ are said to be equivalent if one of the following holds.

Both trees are empty. Or
The two roots hold the same value, and at least one of the following is true.
- (a) The left subtree of $A$ is equivalent to the left subtree of $B$ , and the right subtree of $A$ is equivalent to the right subtree of $B$ . Or
- (b) The left subtree of $A$ is equivalent to the right subtree of $B$ , and the right subtree of $A$ is equivalent to the left subtree of $B$ .

In other words, if you are allowed to freely swap the left and right subtree at every node, two trees are equivalent when they can be made identical in both shape and node values.

Given two binary trees, write a program that determines whether they are equivalent.

Input

The first line contains the number of test cases $T$ .

Each test case consists of two lines, and each line describes one tree to compare.

Each tree is given in post-order. An empty subtree is written as nil, and every node's data is a single uppercase letter. Each line always ends with end.

For example, one tree written in post-order looks like this.

nil nil nil G F nil nil C nil nil E nil D B A end

Output

For each test case, print true if the two trees are equivalent and false otherwise, one result per line.

Examples3

Example 1

Input

2
nil nil nil G F nil nil C nil nil E nil D B A end
nil nil C nil nil E nil D B nil nil G nil F A end
nil nil nil E D nil nil C B nil nil nil G F A end
nil nil nil E C nil nil D B nil nil nil G F A end

Expected output

true
false

Example 2
Input
```
1
nil end
nil end
```
Expected output
```
true
```
Example 3
Input
```
1
nil nil A end
nil nil A end
```
Expected output
```
true
```