How do I find the coordinates of the nodes in a binary tree given as a heap in the input?
<p>Given a heap as input, such as:</p>

<pre><code>1 2 3 - 5 - 7
</code></pre>

<p>Where '-' represents an empty node, I want to find the coordinates of the nodes, which would for the input above be:</p>

<pre><code>[1, 0] [0, 2] [2, 2] [-1, -1] [1, 4] [-1, -1] [3, 4]
</code></pre>

<p>The rules for the coordinate transform is as follows:</p>

<ul>
<li>There should be 1 row of space between each "layer" of the tree, meaning we increment the Y value with 2 for each layer.</li>
<li>The leftmost node should have it's X-coordinate = 0.</li>
<li>There should be at least one space between each node.</li>
<li>All coordinates should be whole numbers.</li>
<li>If a root node has two children, the root should be placed in the middle of it's two children. </li>
<li>If a root node only has one child, the child should be placed one left or one right of the root, depending on it being the left or right child of the root.</li>
<li>If a root node has two subtrees then all the x-coordinates to the nodes of the right subtree be bigger than the x-coordinates to the nodes of the left subtree</li>
<li>An empty node should have the coordinates [-1,-1]</li>
</ul>

<p>I can't for the life of me figure out how I would solve this issue, so any help would be greatly appreciated.</p>

<p>If you look at a heap, you'll notice that each level has twice as many nodes as the previous level. So you have the progression 1, 2, 4, 8, 16, etc.</p>

<p>Given a node's index in the input array, you can easily determine the level it's on by taking the base-2 logarithm of the index and rounding down. That is, if we use 1-based indexing, then:</p>

<pre><code>log2(1) = 0
log2(2) = 1
log2(3) = 1
log2(4) = 2
log2(5) = 2
log2(6) = 2
log2(7) = 2
</code></pre>

<p>Multiply those values by 2 to get your <code>Y</code> coordinate.</p>

<p>For the <code>X</code> coordinates, if you take an index and subtract the number of nodes that occur on all levels above it, you have the index of that item <em>on its row</em>. Consider the 4th (1-based) item in your list. You know that it's at level 2. The number of nodes that come before it, then is <code>(2^2)-1</code>, or 3. And <code>4-3 = 1</code>. So the 4th item in the list is at index 1 on its level.</p>

<p>It's unclear from your question how you want to transform the row indexes. It looks like on your last row the X coordinates would be 0, 1, 2, 3 if all of the items had values. If that's how you want to do each row, then you just subtract 1 from the calculation described in the previous paragraph.</p>

python heap binary-tree