Selecting a subtree in an array representation of a binary tree

Question

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.

Answer 1

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.

Answer 2

@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.