SkolemBinaryTree

A Skolem sequence of order n is a sequence of length 2n that contains each of the numbers 1, 2, ..., n exactly twice and has the following property: for each i, the distance between the two copies of the number i is exactly i. (The distance is measured as the difference between their indices.)

For example, {1, 1, 3, 4, 2, 3, 2, 4} is a Skolem sequence of order 4. You may note that the 1s are at distance 1 from each other, the 2s are at distance 2, and so on.

For some values of n, there is no Skolem sequence of order n. For example, there is no Skolem sequence of order 3. That's why we decided to look at a more general class of objects: Skolem binary trees.

A Skolem binary tree of order n is a binary tree that contains exactly 2n nodes. Each node contains a positive integers. Among those integers, each of the numbers 1, 2, ..., n occurs exactly twice. Additionally, for each i, the distance between the two nodes that contain the number i must be exactly i.

For example, this is a valid Skolem binary tree of order 3:

  3
 / \
2   2
     \
      1
     / \
    3   1

You are given the int k. Find and return one possible Skolem binary tree of order k.

It is guaranteed that there is always a solution. If there are multiple valid solutions, you may choose any one of them.

For simplicity, we will not care about the way your tree is rooted. This means that you can produce any undirected tree in which each node has degree at most 3. Once you have chosen such a tree, the return value is computed as follows:

1. Label the vertices of your tree 0, 1, ..., 2n-1 in such a way that for each i, the two vertices that contain the number i will get labels 2i-2 and 2i-1.
2. Construct a list of edges of your tree: for each edge, in an arbitrary order, list the labels of the two vertices it connects.
3. Return that list as a int[] with 2*(2n-1) elements.

In other words, the return value should have the form {a[0], b[0], a[1], b[1], a[2], b[2], ...} where the a[i] and b[i] are such that for each i, in your tree the vertices with labels a[i] and b[i] are connected by an edge.