Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

Question

Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here. As highlighted by the lack of a 7*2^64/8 term it is not necessarily full, but it is always complete. The nodes are stored in numerical order (in-order) in a list of which I know the size, and I have the index (call it the in-order index) of a node in that sorted list.

I'm trying to get the index (call it level-order index) of that same node if the array was stored according to the breadth-first traversal order (level-order) of the tree instead. In the example, the tree root would have level-order index 0 and in-order index 3.

What I've found already is that the level-order index consists of two parts:

• A base part which is the amount of nodes contained in the perfect tree above the level in which the node resides.
• An offset part which is the amount of nodes to the left of this node in the level in which it is contained.

Summed together, they produce the level-order index.

I have no idea how to find either of these parts from the in-order index. Of course, it is possible by iterating the tree programmatically, but since the exact layout and contents of the entire tree are known simply from the amount of nodes that it contains, I was wondering whether a mathematical relation between these two indices holds. Does anyone have an idea?

Answer 1

I think it is possible by rescaling the in-order index to what it would be in a complete and full (perfect) tree, i.e. $perfect\_index = index*\frac{ceil_2(size + 1)}{size}$ where $ceil_2(arg)$ computes the next power of two of $arg$.

Then, the level at which this perfect-tree in-order index sits is given as follows: $level = \left \lfloor{log_2(size)}\right \rfloor - nr\_divisible_2(perfect\_index + 1)$ where $nr\_divisible_2(arg)$ computes the number of times $arg$ is divisible by 2. This works because it seems like in a perfect tree, the number of times the $index + 1$ of a node is divisible by 2 corresponds to the inverse zero-indexed level number of the level it is contained in. $1 + \left \lfloor{log_2(size)}\right \rfloor$ represents the total number of levels ($nr\_levels$) in a complete tree, so that minus the inverse level index minus 1 should give the zero-indexed level index in narrow-to-wide (top to bottom) tree orientation.

Then, the numerical spacing between in-order node indices in zero-indexed top-to-bottom level $L$ is 2 for the bottom level, 4 one up, 8 one up etc, in other words: $spacing = 2^{nr\_levels - L}$. For a 1-indexed in-order index, there is an additional spacing of $\frac{spacing}{2}$ at the beginning of the level. The horizontal offset of the node into the level is therefore given by $h\_offset = \frac{perfect\_index + 1 - \frac{spacing}{2}}{spacing}$.

Lastly, the amount of nodes preceeding the level this index is contained in is given by the size of a perfect tree of depth $nr\_levels - 1$, which is $base = 2^{nr\_levels}−1$.

The zero-indexed level-order index into the perfect tree should now be $base + h\_offset$. Since the level-order index of the first $size$ (counted in breadth-first traversal order) nodes is the same whether the tree is perfect or complete, I think this index will also be the level-order index into the complete tree.

Note that I have no proof of any of this, and have not tested it yet. Specifically, what worries me most is the rescaling at the beginning and if that is allowed/will work at all. The rest might contain errors but is not fundamentally flawed I think.