Problem A
Climbing Sloths

The Cool Climbing Sloths Consortium (CCSC) is holding their annual sloth climbing contest. Sloths from far and wide have come to test their prowess in ascending trees of various designs. May the “fastest” (perhaps “least slow” would be more accurate) sloth win!

Since there are so many sloths in the contest, the contest organizing committee has decided to produce the trees computationally. They will generate a number of binary search trees, which will then be produced into physical structures for the sloths to climb. However, to ensure the contest is fresh and exciting, they don’t want to use the same tree more than once. They need a way of determining whether any pair of trees are structurally identical.

Two trees are considered structurally identical if they share the same node layout, regardless of the values stored in the nodes. Furthermore, since these trees will be produced into physical structures, two trees are also considered structurally identical if mirroring one about its root produces a tree with the same node layout as the other.

For example, the two trees below are structurally identical:

    6           7
   / \         / \
  1   8       2   9
   \           \
    3           5

The two trees below are also structurally identical, since mirroring one about its root produces the same node layout as the other:

    6           7
   / \         / \
  1   8       2   9
   \             /
    3           8


Input consists of two lines. Each line contains between $1$ and $10^4$ space-separated, distinct integers, where each integer is between $1$ and $10^5$. Each line represents the binary search tree that is formed by inserting those integers in that order into an initially empty tree.


Output YES if the input represents structurally identical trees, or NO if not.

Sample Input 1 Sample Output 1
6 8 1 3
7 2 9 8
Sample Input 2 Sample Output 2
6 8 1 3
7 2 8 9

Please log in to submit a solution to this problem

Log in