An empty tree is represented by null. A non$-$empty tree is represented by an object

representing its root. The attribute x holds the ID of the node, whereas attributes $1$ and r

hold the left and right subtree, respectively. For example, in the figure above, the tree is

rooted in node $3.$

Notice that the binary tree data structure is correct if and only if each node is a subtree

of exactly one other node, except for the root, which cannot be a subtree of any other

node.

Nodes X and Y are connected if node X points to node Y as its left or right subtree or if

node Y points to node X as its$-$ left or right subtree. For example, in the figure above:

$$ nodes $1$ and $6$ are connected,

$$ nodes $4$ and $5$ are connected,

$$ nodes $3$ and $4$ are not connected.

The binary tree can be rerooted by changing its root to another node, which is a leaf. The

rerooted tree should maintain all the connections of the original tree $-$ if nodes X$,$ Y are

connected in the original tree then nodes X$,$ Y should remain connected in the rerooted

tree.

The order of subtrees in the rerooted tree is not significant. In other words, it is

permissible to swap the left and right subtree for each node.

For example, the figure below shows the tree from the previous example rerooted to

node $2.$

Test O