Getting parent of a vertex in a perfect binary tree

Question

I've got a perfect binary tree that's enumerated the post-order way. An example of such tree would be

                         15
                 7               14
             3       6       10      13
           1   2   4   5    8  9   11  12

The size of the tree is known to me. I'm looking for a formula or a simple algorithm that would take a single number as an input (the ID of the vertex I'm interested in) and return also a single number - the ID of the parent. It's quite easy to traverse the tree from the top and get the result in O(log n). Is there a faster solution? I'm mostly interested in the leaves, so if there's a solution for the special case, bring it on too.

Perforated

Is your tree a Binary Search Tree or just a Binary Tree? The example given doesn't have the search property but a plain Binary Tree can't find an element in O(log n), so which is it? – Howard

@DAnstahr u cant even do it in O(logn) on the example tree as it is not BST – Tingly

@Perforated i think your data structure is max heap and for max heap it is O(N) to find element or its parent. – Tingly

Please forget about the data that's stored inside. It's not relevant to the question. Just look at the post-order enumeration. The particular order might bring a simple mathematical formula for this. – Perforated

@Perforated now i got what u really want , sorry for confusion , yes there os trivial way for calculating in O(logn) and most probably there must be one for calculating in O(1) using maths – Tingly

Yes, it seems natural, but I can't get it myself. – Perforated

could not you label those vertices bit different? first level: 1 second 2, 3; third: 4, 5, 6, 7 etc than the function connecting child to parent is trivial... – Folger

@arturgrzesiak: That's unfortunately not possible. The tree grows to the right and reindexing the whole tree would be too costy. – Perforated

@downvoter : Can you please explain? – Perforated

Are you allowed to query for the IDs of the children? – Sewellyn

A little late to the party, but would it be allowed to get the value with a quick python script? – Daloris

Answer 1

Parent index could be found in O(log^* n) time and O(1) space.

Here log^* n means iterated logarithm: the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

Actually that may be done even faster - in O(1) time if we could afford O(n) space for a large lookup table (storing parent index for each node in the tree).

Below I'll sketch several algorithms that do not need any extra space and give result in O(log n) worst case time, O(log log n) expected time, O(log log n) worst case time, and O(log^* n) worst case time. They are based on following properties of post-order indexes for perfect binary tree:

1. All indexes on the leftmost path of the tree are equal to 2ⁱ-1.
2. Indexes of every right child of the node on the leftmost path are equal to 2ⁱ-2.
3. Any node on the leftmost path and its right sub-tree are labeled with indexes having most-significant non-zero bit on the same position: i.
4. Left sub-tree of any node on the leftmost path contains 2ⁱ-1 nodes. (Which means after subtracting 2ⁱ-1 we'll get a node that is positioned in similar way relative to its parent, has the same depth, but is closer to "special" nodes satisfying properties #1 and #2).

Properties #1 and #2 give simple algorithms to get parent node for some nodes of the tree: for indexes of the form 2ⁱ-1, multiply by 2 and add 1; for indexes of the form 2ⁱ-2, just add 1. For other nodes we could repeatedly use property #4 to come to the node satisfying property #1 or #2 (by subtracting sizes of several left sub-trees), then find some parent node located on the leftmost path, then add back all previously subtracted values. And property #3 allows to quickly find size of which sub-trees should be subtracted. So we have following algorithm:

1. While ((x+1) & x) != 0 and ((x+2) & (x+1)) != 0 repeat step 2.
2. Clear most-significant non-zero bit and add 1. Accumulate the difference.
3. If ((x+1) & x) == 0, multiply by 2 and add 1; otherwise if ((x+2) & (x+1)) == 0, add 1.
4. Add back all differences accumulated on step 2.

For example, 12 (in binary form 0b1100) is transformed on step #2 to 0b0101, then to 0b0010 (or 2 in decimal). Accumulated difference is 10. Step #3 adds 1 and step #4 adds back 10, so the result is 13.

Other example: 10 (in binary form 0b1010) is transformed on step #2 to 0b0011 (or 3 in decimal). Step #3 doubles it (6), then adds 1 (7). Step #4 adds back accumulated difference (7), so the result is 14.

Time complexity is O(log n) - but only when all elementary operations are executed in O(1) time.

To improve time complexity we could perform several iterations of step #2 in parallel. We could get n/2 high-order bits of the index and compute population count on them. If after adding the result to the remaining low-order bits the sum does not overflow to these high-order bits, we could apply this approach recursively, with O(log log n) complexity. If we have an overflow, we could roll back to the original algorithm (bit-by-bit). Note that all set low-order bits should be also treated as overflow. So the resulting complexity is O(log log n) expected time.

Instead of rolling back to bit-by-bit we could handle overflow using binary search. We could determine how many high-order bits (less than n/2) are to be selected so that we either have no overflow or (as for index 0b00101111111111) the number of selected non-zero high-order bits is exactly 1. Note that we do not need to apply this binary search procedure more than once because second overflow would not happen while number of bits in the number is greater than O(log log n). So the resulting complexity is O(log log n) worst case time. All elementary operations are assumed to be executed in O(1) time. If some operations (population count, leading zero count) are implemented in O(log log n) time, then our time complexity increases to O(log² log n).

Instead of dividing bits of the index into two equal sets we could use different strategy:

1. Compute population count of the index and add it to index value. Most significant bit that changed from 0 to 1 determines separation point for high-order/low-order bits.
2. Compute population count on high-order bits, then add the result to low-order bits.
3. If "separation" bit is non-zero and ((x+1) & x) != 0 and ((x+2) & (x+1)) != 0, continue from step #1.
4. If all low-order bits are set and least significant high-order bit is set, process this corner case as right child.
5. If ((x+1) & x) != 0 and ((x+2) & (x+1)) != 0, also process this as right child.
6. If ((x+1) & x) == 0, multiply by 2 and add 1; otherwise if ((x+2) & (x+1)) == 0, add 1.

If condition of step #3 is satisfied, this means addition on step #2 resulted in carry to "separation" bit. Other low-order bits represent some number that cannot be greater than original population count. Number of set bits in this number cannot be greater than logarithm of population count of the original value. This means that number of set bits after each iteration is at most logarithm of the number of set bits on previous iteration. Therefore worst case time complexity is O(log^* n). This is very close to O(1). For example, for 32-bit numbers we need approximately 2 iterations or less.

Every step of this algorithm should be obvious, except probably step #5, correctness of which is to be proven. Note that this step is executed only when adding population count results in carry to "separation" bit but adding population count of only high-order bits does not result in this carry. "Separation" bit corresponds to value 2ⁱ. Difference between population count of all bits and population count of only high-order bits is at most i. So step #5 deals with a value at least 2ⁱ-i. Let's apply bit-by-bit algorithm to this value. 2ⁱ-i is large enough so that bit i-1 is set. Clear this bit and add 1 to the value in bits 0..i-2. This value is at least 2^i-1-(i-1) because we just subtracted 2^i-1 and added 1. Or if we move index one position to the right, we have again at least 2ⁱ-i. If we repeat this procedure we'll always find non-zero bit at position i-1. Each step gradually decreases difference between value in bits 0..i-1 and nearest power of 2. When this difference comes to 2, we could stop this bit-by-bit algorithm because current node is clearly a right child. Since this bit-by-bit algorithm always comes to the same result, we could skip it and always process current node as a right child.

Here is C++ implementation of this algorithm. More details and some other algorithms could be found on ideone.

uint32_t getMSBmask(const uint32_t x)
{ return 1 << getMSBindex(x); }

uint32_t notSimpleCase(const uint32_t x)
{ return ((x+1) & x) && ((x+2) & (x+1)); }

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;
    uint32_t bit = x;

    while ((x & bit) && notSimpleCase(x))
    {
        const uint32_t y = x + popcnt(x);
        bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        const uint32_t z = (x & mask) + popcnt(x & ~mask);

        if (z == mask && (x & (bit << 1)))
            return node + 1;

        x = z;
    }

    if (notSimpleCase(x))
        return node + 1;
    else
        return node + 1 + (((x+1) & x)? 0: x);
}

If we need to find parent only for a leaf node, this algorithm and code may be simplified. (Ideone).

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;

    while (x > 2)
    {
        const uint32_t y = x + popcnt(x);
        const uint32_t bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        x = (x & mask) + popcnt(x & ~mask);
    }

    return node + 1 + (x == 1);
}

Phox

Thank you for your immense effort. The bounty is yours. – Perforated

@Evgeny Kluev Could you elaborate the intuition behind the while loop ? – Optician

@TLJ: I think everything is already explained in the answer. As for the while loop, its body implements steps 1&2 of the algorithm, and steps 3&4 give conditions to terminate the loop. – Phox

@EvgenyKluev the algorithm works great! thanks for that, but I just don't get it yet. For example in one case, why do we multiply by 2 and add 1 and add those to the diff and it resolves to the parent node. I'll try to read it over. – Optician

That is an incredibly complex solution :) I layed out a basic tree in a spreadsheet... docs.google.com/spreadsheets/d/… And looked at the bit pattern. Just have to find the first 0 bit, and set it, and clear the bit above it... (JS) function upTree( N ) { var n; for( n = 0; n < 32; n++ ) if( !(N&(1<<n)) ) break; return (N & ~((0x3)<<n)) | ( 0x01 << n ) } (or just & ~ the one bit, and | the other.) I noticed that each level has a column it that is 0 followed by all bits on towards the parent. – Audubon

Answer 2

function getParent(node, size)
{
    var rank = size, index = size;

    while (rank > 0) {
        var leftIndex = index - (rank + 1)/2;
        var rightIndex = index - 1;

        if (node == leftIndex || node == rightIndex) {
            return index;
        }

        index = (node < leftIndex ? leftIndex : rightIndex);
        rank  = (rank - 1)/2;
    }
}

It starts from the root, deciding which branch to step down into, and repeats until the node is found. The rank is the index of the leftmost node on the same level: 1, 3, 7, 15, ..., k^2 - k + 1.

The input parameters are:

• node – The index of the node you want the parent of. (1-based)
• size – The index of the root node; 15 in your example.

Example:

>>> r = []; for (var i = 1; i <= 15; i++) r.push(parent(i,15)); r;
[3, 3, 7, 6, 6, 7, 15, 10, 10, 14, 13, 13, 14, 15, undefined]

Illimani

This solution indeed works, but it's the log(n) one I mentioned in the OP. – Perforated

Answer 3

Let's take a look at your tree:

                     15
             7               14
         3       6       10      13
       1   2   4   5    8  9   11  12

Rewrite label n as 15-n. Then we get:

                     0
             8               1
         12      9        5       2
       14  13  11  10   7   6   4   3 

which could also be written as

                     0
             +8              +1
         +4      +1      +4      +1
       +2  +1  +2  +1  +2  +1  +2   +1 

Well there's a pattern for you. So in this labelling scheme, left children are 2^(i+1) more than their parents, where i is the height of the child, while right children are 1 more than their parents. How can we work out the height of a child though, and whether it's a left or right child?

Unfortunately, I can't work out any way to get this information without working out the entire path to the node, which means logarithmic time. You can however deduce the path to the node directly from the node's label (demonstrated here for a height-3 tree):

• Suppose we have a label n
• If n == 0, it's the root.
• Otherwise:
  • If n - 8 >= 0, it's in the left subtree of the root. Set n = n-8.
  • If n - 8 < 0, it's in the right subtree of the root. Set n = n-1.
• If n == 0 now, it's the root of whatever subtree was discovered in the last step.
• Otherwise:
  • If n - 4 >= 0, it's in the left subtree of whatever subtree was discovered in the last step. Set n = n-4
  • If n - 4 < 0, it's in the right subtree of whatever subtree was discovered in the last step. Set n = n-1.
• Et cetera until you've got down to testing n-1 >= 0.

You could do all this using bit arithmetic and -1s and it'd be spectacularly fast in real-world terms (calculating this in a trillion-node tree would only take ~12 times longer than a 10 node tree (ignoring memory issues)) but it's still going to be logarithmic time.

Anyway, once you know the height of the label though and whether it's a left or right child, you can easily calculate the label of the parent using the relations I mentioned earlier.

Agna

Answer 4

import math
def answer(h,q=[]):
    ans=[]
    for x in q:
        if(True):
            curHeight=h;
            num=int(math.pow(2,h)-1)
            if(x==num):
                ans.append(-1)
            else:
                numBE=int(math.pow(2,curHeight)-2)
                numL=int(num-int(numBE/2)-1)
                numR=int(num-1)
                flag=0
                while(x!=numR and x!=numL and flag<10):
                    flag=flag+1
                    if(x>numL):
                        num=numR
                    else:
                        num=numL
                    curHeight=curHeight-1
                    numBE=int(math.pow(2,curHeight)-2)
                    numL=num-(numBE/2)-1
                    numR=num-1
                ans.append(num)
    return ans

Surely

Why are you using a flag variable? In which case it will be helpful? – Grammar

Answer 5

If you're allowed to query for the IDs of the children of a node, you can do some useful things.

Trivial case 1: if x = size, it is the root.

Trivial case 2: if x is a leaf (query for child IDs to find out), try x + 1. If x + 1 is not a leaf (an other query for child IDs), x was the right child of x + 1. If x + 1 is a leaf, x is the left child of x + 2.

For internal nodes: the children of x are x - 1 (right child) and x - (1 << height(x) - 1) (left child, the right child is a perfect binary tree so it has 2^h-1 nodes). So, using the difference between x and left_child(x), the height of x can be determined: height(x) =ctz(x - left_child(x)), but it's really the size of that subtree that's required so you'd take 1 << height anyway, so the ctz can be dropped.
So the parent of x is either x + 1 (iff right_child(x + 1) == x) or the parent of x is
x + (x - left_child(x)) * 2 (otherwise).

That's not as nice as just doing math on the ID, but assuming you're allowed to ask for the children of a node in constant time, this is a constant time algorithm.

Sewellyn

About the children of a node : I think it's not possible to presume that. Let's say an array is thrown on me and the only thing I know is that the array represents a perfect post-order binary tree (e.g. array[15] is the root for the example given in the OP). I have a feeling that these two problems (getting the parent and getting children) could be pretty much equivalent to each other. – Perforated

@Perforated yes, they're pretty much equivalent. You can also compute both children if you have a node and its parent. If you have only that array, it's not going to work of course. That's a shame, I thought I had a good trick here :) – Sewellyn

Answer 6

Sorry for the non-answer answer, but I don't think it's possible to do it in less than O(log n), even allowing for constant-time arithmetic and bitwise logical ops.

Each bit in the node's index potentially has an effect on nearly every left/right/stop decision in the traversal from the node to the root, including the first one. Moreover, examining the indices of the nodes at each level of the tree, they are aperiodic (and not only in powers of 2). This means (I think) that a constant number of arithmetic ops is not sufficient to identify the level, or whether the node is a left or right child.

It's a fascinating problem, though, and I'd love to be proven wrong. I just scoured my copy of Hacker's Delight -- I had high hopes for some of the exotic number bases they play with, but nothing quite fit.

Unwisdom

#20405846 uhmm... yes, I guess the bit search is O(log n)... (nevermind I guess) – Audubon

Answer 7

python, return -1 for root node:

def find_parent(h, n):
parent = -1
root = 2 ** h -1
while root >= n:
    left_top = root - 2 ** (h-1)
    right_top = root - 1
    print(f"parent:{parent}, root:{root}, left:{left_top}, right:{right_top}")
    if n >= root:
        return parent
    if n == left_top or n == right_top:
        return root
    if n < left_top:
        parent = root
        root = left_top
        h -= 1
    if n > left_top:
        parent = root
        root = right_top
        h -= 1
return parent

Revival