CODEWITHSUNDEEP
binary-treesegment-tree
Lisbeth
Lisbeth

Reputation: 151

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,

(↓ 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

Upvotes: 1

Views: 1057

Answers (2)

ynn
ynn

Reputation: 4817

0. TL;DR

You can use this, which takes O(1) time (playground):

const n: usize = 8; //the number of leaves

fn depth(i: usize) -> u32 {
    (i + 1).ilog2()
}

fn get_leftmost_leaf_of_subtree(i: usize) -> usize {
    //`(2 * n - 1) - 1` is the index of the rightmost leaf of the entire tree.
    //We choose this index just to calculate the depth of the lowermost layer.
    2usize.pow(depth(2 * n - 1 - 1) - depth(i)) * (i + 1) - 1
}

fn get_rightmost_leaf_of_subtree(i: usize) -> usize {
    2usize.pow(depth(2 * n - 1 - 1) - depth(i)) * (i + 2) - 2
}

Let's prove

  • the algorithm is correct

  • and its time complexity is O(1).

1. O(log(N)) Algorithm

If you use 0-based indices, the indices of the left and right children of the node i are 2 * i + 1 and 2 * i + 2 respectively. This calculation takes O(1).

If you start from the node i and repeatedly move to the left child of the current node, you will finally reach the leftmost leaf node of the subtree whose root node is i.

Similarly, if you repeatedly mode to the right child, you will finally reach the rightmost leaf node of the subtree.

The number of times you need to go down is given as O(log_2(N)) as the current index is doubled every time you go down.

So the time complexity of the algorithm is O(1) * O(log_2(N)) = O(log(N)).

2. O(1) Algorithm

According to the algorithm above, you will repeatedly calculate 2 * i + 1 (or 2 * i + 2), where i is the index of the current node.

This corresponds to this nonhomogeneous linear recurrence with a constant coefficient a_{n+1} = 2 * a_n + p, where p = 1 or p = 2. The general term is given as a_n = 2^n (a_0 + p) - p.

For example, if you go down n times to the left child from the node i, the final index is calculated as a_n = 2^n (i + 1) - 1, taking O(1) time.

And the value of n when you repeatedly move down to the leftmost leaf node of the subtree is given by depth(leaf node) - depth(i).

If you (temporarily) use 1-based indices, the depth of the node i can be calculated as log_2(i + 1) in O(1), where the depth of the root node is defined as 0.

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

Thus the time complexity of this algorithm is O(1) * O(1) = O(1).

Upvotes: 0

trincot
trincot

Reputation: 350310

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 24-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:

Index Value Position Position (binary) Shift Range In decimal Indices
0 15 1 0001 1*** 1000-1111 8-15 7-14
1 10 2 0010 10** 1000-1011 8-11 7-10
2 5 3 0011 11** 1100-1111 12-15 11-14
3 3 4 0100 100* 1000-1001 8,9 7,8
4 7 5 0101 101* 1010-1011 10,11 9,10
5 5 6 0110 110* 1100-1101 12,13 11,12
6 0 7 0111 111* 1110-1111 14,15 13,14

Upvotes: 1

Related Questions