Symmetric Binary Tree Check

You are given a binary tree with n nodes. Each node is described by a tuple of three integers: u, v_L, and v_R, where u is the node number, and v_L and v_R represent the left and right child of the node respectively. A value of -1 indicates the absence of a child.

Your task is to determine whether the binary tree is symmetric.

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. In mathematical terms, if you denote the left and right child arrays as:

\( left[i] \) and \( right[i] \), then the tree is symmetric if for the root node 1, the subtrees satisfy \[ \text{isMirror}(left[1], right[1]) = true, \]

where the recursive function \( \text{isMirror}(L, R) \) is defined as:

[ \begin{aligned} \text{isMirror}(L, R) &= true && \text{if } L = -1 \text{ and } R = -1, \ \text{isMirror}(L, R) &= false && \text{if } L = -1 \text{ or } R = -1, \ \text{isMirror}(L, R) &= false && \text{if } L \neq R, \ \text{isMirror}(L, R) &= \text{isMirror}(left[L], right[R]) \text{ and } \text{isMirror}(right[L], left[R]) && \text{otherwise.} \end{aligned} ]

If the tree is symmetric output Symmetric, otherwise output Not symmetric.

inputFormat

The first line of input contains an integer n, representing the number of nodes in the binary tree. Each of the next n lines contains three integers u, v_L, v_R separated by spaces, describing a node and its children. A value of -1 indicates that the child does not exist.

outputFormat

Output a single line: Symmetric if the binary tree is symmetric, otherwise Not symmetric.

1
1 -1 -1

Symmetric