Intuition behind $2i+1\ 2i+2$ formula for converting array to a complete binary tree

Question

I have tried really hard to come up with the formula for converting an array of elements to a binary tree, but I have failed.

I need some help understanding the intuition behind how the formula $2i+1\ 2i+2$ works, and how you would come up with such a formula yourself.

I will layout my way of thinking and what I was trying to do, maybe someone can help me pointing out the gap in my knowledge and how a problem like this should be approached.

Problem:

Given an array of elements convert it to a complete binary tree.

Example:

$$array = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]$$

The binary tree formed would be:

What my understanding is/What I was trying:

• At each level in a complete binary tree the number of nodes increase by the a power of $2$
• I can go the next level by multiplying by $2$.
• I tried to reconstruct the tree using the powers of $2$

• Now that I know the formula of $2i+1$ and $2i+2$ I can see that I can do some simple simplifications from the tree to fit the use case.

Example:

$2^3+3 = 2(2^2+1)+1$

$2^3+3 = 2^3+2^1+1 = 2(2^2+1)+1$

$2^3-1 = 2^3-2+1 = 2(2^2-1)+1$

But how are you suppose to figure this out yourself ? What did I miss ?

Thanks.

Answer 1

Here's how you might reconstruct this idea. First of all, instead of indexing from 0 we will choose 1, because that makes the pattern a little clearer.

With your binary tree, write the indexes of each node in binary. Then, for each node, its 0s and 1s tell you how to reach the target element, starting at the top and making a series of left/right choices.

If we call the root element "1" then its children are "10" and "11". Their children are respectively "100" and "101"; and "110" and "111". This breadth-first pattern is a natural way to assign numbers and something you might well come up with from first principles. It has the nice property that the numbering scheme is stable when stuff is added on to the bottom of the tree, which wouldn't be the case with a depth-first assignment.

Once you've drawn this picture, you can see that there is a relationship between the binary value for a node and those for its children. We find the general pattern that to go left, you shift bits to the left and end with a 0; to go right, you shift bits to the left and add a 1. This gives you formulae mapping $i$ to $2i$ or $2i+1$ respectively. Conversely, you can reach the parent of a node by shifting its bits to the right (so the least significant one drops off).

As you are using a 0-based array, everything is shifted down by 1. To produce a correct formula, we have to do some shuffling around between the 1-based and 0-based representations. The structure is that if $i$ is a 0-based index, then we will add 1 to $i$ to make it a 1-based index, apply the original formula, then subtract 1 from the result to give us the required 0-based index. Then for going left, $i$ maps to $2(i+1) - 1 = 2i + 1$. For going right, we get $2(i+1) + 1 - 1 = 2i + 2$.

Answer 2

It's just counting. If we are at a level $n$ in a complete binary tree then there are $2^n$ elements in our level and $2^{n+1}$ elements in the level below. Our index $k$ will be such that $2^{n-1}+1\le k\le 2^n$.

To get to our first child, we will have to add $$2^n-k$$ to our position $k$ to get to the end of our level and add $2p+1$ to get to our first child. Here, $p$ is the number of predecessors in our level. We add $2p$ because each predecessor has two children and then add $1$ to get to our first child. Note that $p=k-2^{n-1}$ because $k$ is the $k$th element after the previous row.

This gives $$ \begin{align} \text{Index}&=\underbrace{k}_{\text{start}}+\underbrace{2^n-k}_{\text{to get to end of level}}+\underbrace{2(k-2^{n-1})+1}_{\text{to get to first child}} \\ & = k+2^n-k+2k-2^n+1 \\ & = 2k+1 \end{align} $$