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?