Given a perfect, balanced and complete binary tree of height H with its nodes enumerated depth-first in-order, what formula can you use to calculate the depth of a node given its index in constant time?
[Math] Determine depth of node in perfect binary tree with depth-first in-order enumeration
graph theorytrees
Best Answer
Given the binary representation of the index $i=x_0x_1x_2...x_n$ where $x$ is a binary constitutive digit of $i$.
1-If $i$ is odd where the last digit $x_n$ is set the indexed spot is a leaf wich means the depth is $H$
2-If the last but one digit is set, the level is H-1
... going this cadence helps us to generate a rule.
The depth $D=\begin{cases} H\ i\ is \ odd \\ H-1\ i=2+4k \\ H-2\ i=4+8k \\....\\ H-n\ i=2^n+2^{n+1}k \end{cases}$
How about a linear time algorithm ?
I believe this can be done basing on binary structure of $i$, from informations above and what is prealably provided by @RoryDaulton , the actual depth $D$ can be defined in order of first bit set from right to left .....10000...0.
Which reminds me quite of this answer where i could succeed to get the first '1' right to left by xoring the negation of this number (reversing its digits) with its sum to 1 .
exemple: i=$(10)_{10}=(1010)_2$
$(\overline{i}\bigoplus (\overline{i}+1))=0101\bigoplus 0110=11$
The binary log of this result gives the standing of '1' been sought for, here, $\lfloor log_2((11)_2)\rfloor=log_2((11)_2+1)-1=1$ means the depth $D=H-1=4-1=3$