How to determine the indexes of the leaves in a given subtree in a complete binary tree?

I have a complete binary tree with 0-based indices:

                             0
                 _________ /   \ __________
               /                            \
             1                                2
           /   \                           /     \
         /       \                       /         \
       3           4                   5             6
     /   \       /   \               /   \         /   \
    7     8     9     10           11     12     13     14

The indices of the leaf nodes are 7, 8, 9, ..., 14.

Given a node index i, how can we find the indices of the leaf nodes belonging to the subtree whose root node is i?

For example,

• When i == 0, the answer is 7, 8, ..., 14.

• When i == 1, the answer is 7, 8, 9 and 10.

• When i == 4, the answer is 9 and 10.

_{(↓ Editor's note: The information below is completely irrelevant to the question itself. However, I don't remove it as the information is referred to from the accepted answer.)}

By the way, we assume the nodes have these values (breadth first):

[15, 10, 5, 3, 7, 5, 0, 1, 2, 3, 4, 5, 0, 0, 0]
 ↑                                           ↑
root note                            rightmost leaf node

As the array represents a perfect binary tree, i.e., where all internal nodes have 2 children, and all the leaves are located at the same depth, the array length will always be a power of 2 minus 1. In the example it is 2⁴-1. That power is the number of levels of the tree... which is one more than the tree's height. Let's call the height ℎ, then the size of the input array is 2^ℎ+1-1.

We can use binary representations of position numbers. With position I mean the index plus 1. So the root has position 1, and its children have positions 2 and 3. Represent each position in binary representation, using ℎ+1 binary digits. So for the example input, you would use 4 digits. To know the range of positions of the leaves below a given position, see how many leading zeroes there are in the position number.

For instance, take position 3 (where the example tree has value 5), which is 0011 in binary with 4 digits. It has 2 leading zeroes.

Now remove those leading zeroes. For the example we get binary 11.

Now complete these digits at the right with any digits to have again 4 digits. This represents the range of positions of the leaves. In the example: 1100 to 1111. You can then turn that back to decimal and subtract 1 to get the indices: 11,12,13,14.

Here is a table that does this calculation for all the internal nodes in your example: