2
$\begingroup$

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?

An example of a perfect binary tree with nodes enumerated depth-first in-order

$\endgroup$
7
  • $\begingroup$ It is not possible to "calculate the depth of a node given its index" since it also depends on the height of the entire tree. (Index $1$ will always have the depth equal to the height of the tree.) We could calculate the height of the node above the bottom of the tree. (Index $1$ will be $0$ levels above the bottom, $2$ will be $1$ level, etc.) Is that what you want? $\endgroup$ Feb 24, 2016 at 12:50
  • $\begingroup$ Which functions are allowable in your "formula"? x86 CPU's have an instruction BSF that can quickly find the height above the bottom of the tree. $\endgroup$ Feb 24, 2016 at 12:53
  • 1
    $\begingroup$ Rory Daulton, I see your point. I have added that the height of the tree is given by the variable H in the original question. $\endgroup$
    – aether
    Feb 24, 2016 at 13:03
  • $\begingroup$ I need a mathematical formula, a reference to a CPU instruction will not help me here. $\endgroup$
    – aether
    Feb 24, 2016 at 13:08
  • 1
    $\begingroup$ I can think of many formulas/algorithms that would run in time at most proportional to the number of bits in the binary representation of $H$ but none in constant time (unless I obscure the repeated calculations in some way). The number of levels of a node above the bottom level of the tree is given by $n$ where the least significant $1$ bit in the binary representation of the index is at the $2^n$'s place. $\endgroup$ Feb 24, 2016 at 19:22

2 Answers 2

0
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Thank you. As I understand it, an algorithm based on this would be linear in the number of levels. Can a constant time solution be proved impossible? I have posted an answer with a suggestion for an algorithm based on your answer (could not figure out to format math in a comment). $\endgroup$
    – aether
    Feb 25, 2016 at 4:42
  • $\begingroup$ Should be 2^(n+1), not 2^(2n) in the last line. $\endgroup$
    – aether
    Feb 25, 2016 at 11:18
0
$\begingroup$

So based the answer from @Agawa001, an algorithm for determining the depth of a node can be devised:

nodeDepth(i):
  for n in range (0, H):
    if ($i + 2^n$) mod $2^{n+1} = 0$: return $H - n$

This runs in $O(H)$, thus $O(log(n))$ where n is the number of nodes in the tree.

I am still not convinced that this cannot be done in constant time. Can it be proven?

$\endgroup$
1
  • $\begingroup$ aether i made supplementary content for so-expected constant time algorithm, plz review. $\endgroup$
    – Abr001am
    Feb 27, 2016 at 19:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .