2
$\begingroup$

Consider a zero-indexed array representation of a binary tree (as in a binary heap), where

  • 0 is the root
  • The left child of i is L(i) = 2*i+1.
  • The right child of i is R(i) = 2*i+2.

Is there a simple predicate S such that S(i,j) means j is in the subtree rooted at i? It should preferably be quickly computable with something like numpy.

For example, A092754 is the set of nodes in the left subtree of the root 0.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

If you change the layout to following:

  • 1 is the root
  • The left child of i is L(i) = 2*i.
  • The right child of i is R(i) = 2*i+1.

then formula is simple: binary index of the node is prefix of binary index of any its descendant, f.e. node with index 0b101 is ancestor of any node with index 0b101...

In order to check this property, you need to find index of highest set bit in both numbers hsbit(x) and perform the check descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor.

Moreover, it seems that your layout is just the same as mine, but with all indexes decremented by 1.

Improve this answer
$\endgroup$
0
$\begingroup$

@Bulat

descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor

This does not appear to work for descendant = 2 (0b10), ancestor = 0, if the index of the highest set bit is in base-0. hsbit(0b10) = 1, hsbit(0) = 0, and (0b10 >> (1-0)) = 0b01, which is not equal to ancestor = 0b0, but descendant = 2 (the first right-child of the root) is definitely a subtree of the root.

The index of the highest set bit must be in base-1.

Improve this answer
$\endgroup$

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.