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.

$\endgroup$
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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