0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ When you say a "full" or "complete" tree, do you mean as per these definitions? $\endgroup$ May 10, 2021 at 11:34
  • $\begingroup$ Yes. The 'complete but not full' example in that link is precisely what I mean. $\endgroup$ May 10, 2021 at 12:42
  • $\begingroup$ You solved it for a full complete tree. Is that right? If so, then this statement is not clear to me: level at which a node is contained is the number of times its in-order index + 1 is divisible by 2. Can you give an example for this? $\endgroup$ May 10, 2021 at 13:04
  • $\begingroup$ That was indeed not clear in my question so I have removed that part for clarity. In my suggested answer I have included the rationale for it if you're interested. $\endgroup$ May 10, 2021 at 13:46

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.