# Selecting a subtree in an array representation of a binary tree

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.

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