October 27, 2017 TCO17: Analysis of Algorithm Semifinals, Pt. 2

Today it turned out that I am not the only Topcoder marathoner who is also a runner. It is tomerun who runs marathons and ultramarathons in real life in addition to Topcoder marathon-style programming competitions. We sit together with him and brainstormed the 250-point problem from yesterday algo Semifinal 2.
The task, available for practice in the arena, is to create a Skolem sequence-like binary tree. That is, you need to connect nodes with numbers from 1 to k, into a binary tree. Each number appears twice in the final tree. Additional requirement is that a distance between 2 nodes with the same number x in them, should be equal to that number x.
This task is even more constructive than the 250-pointer from Semifinal 1. I advise you to try to play with pen and paper before proceeding with the reading.
Spoiler. Did you really take your pen and pencil and tried to solve this task?
First of all, it is clear that we must place 1-1 edge somewhere, along with its nodes. Let us do it in the very beginning. Then we may draw all external edges going to/from these 1’s we have just placed:

Now we may place 2s:

Now the key idea is to forget about 3s and instead place all the even numbers remaining there.
Now we can put the odd numbers in a form of clamp around one of the 2s and 4. That’s it. Or wait, we did not cover the case when there are just 3 numbers. Hopefully it is provided as an example, so we can just hardcode it.
Thanks for reading, and good luck to algo finalists!