1
$\begingroup$

I think you can compute the index of the n^{th} ancestor of the node at index i using the formula: $\lfloor i / 2^n \rfloor$ where $n \in \mathbf{Z}^+$. Note that I am assuming that the parent node is at index 1 for this. Left child nodes have even indexes, and right child nodes have odd indexes. Nodes are number from top to bottom, left to right, with the root node being at the very top and the tree extending downwards.

I know that you can get the index of the parent via $\lfloor i / 2 \rfloor$. The only question is whether the rounding errors can potentially throw off the computation such that I need to compute the ancestor's index like: $\lfloor \cdots \lfloor \lfloor i / 2 \rfloor / 2 \rfloor \cdots / 2 \rfloor$.

My google-fu is failing me at the moment, so hoping one of you can verify one way or the other; extra points for a reference :)

EDIT: Of course, if you shift instead of divide its a moot point. However, I'm attempting to use this equation as part of a mathematical proof about how something can be modeled as a perfect binary tree; and dividing feels a little more appropriate in that context.

$\endgroup$

1 Answer 1

1
$\begingroup$

For any node $i$, its children are $2i$ and $2i+1$.

Using induction, you can prove that its $n^{th}$ level descendants are: $2^{n} \cdot i + j$ for $j \in \{0,\dotsc,2^n-1\}$.

Equivalently, you can say that any descendant $d$ has its $n^{th}$ ancestor $\lfloor d/2^n \rfloor = i$

$\endgroup$
1

Your Answer

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

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