Ion Flux Relabeling

Problem

Oh no! Commander Lambda’s latest experiment to improve the efficiency of the LAMBCHOP doomsday device has backfired spectacularly. The Commander had been improving the structure of the ion flux converter tree, but something went terribly wrong and the flux chains exploded. Some of the ion flux converters survived the explosion intact, but others had their position labels blasted off. Commander Lambda is having her henchmen rebuild the ion flux converter tree by hand, but you think you can do it much more quickly – quickly enough, perhaps, to earn a promotion!

Flux chains require perfect binary trees, so Lambda’s design arranged the ion flux converters to form one. To label them, Lambda performed a post-order traversal of the tree of converters and labeled each converter with the order of that converter in the traversal, starting at 1. For example, a tree of 7 converters would look like the following:

   7
 3   6
1 2 4 5

Write a function solution(h, q) - where h is the height of the perfect tree of converters and q is a list of positive integers representing different flux converters - which returns a list of integers p where each element in p is the label of the converter that sits on top of the respective converter in q, or -1 if there is no such converter. For example, solution(3, [1, 4, 7]) would return the converters above the converters at indexes 1, 4, and 7 in a perfect binary tree of height 3, which is [3, 6, -1].

The domain of the integer h is 1 <= h <= 30, where h = 1 represents a perfect binary tree containing only the root, h = 2 represents a perfect binary tree with the root and two leaf nodes, h = 3 represents a perfect binary tree with the root, two internal nodes and four leaf nodes (like the example above), and so forth. The lists q and p contain at least one but no more than 10000 distinct integers, all of which will be between 1 and 2^h-1, inclusive.

Test Cases

Your code should pass the following test cases. Note that it may also be run against hidden test cases not shown here.

Input:
solution.solution(3, [7, 3, 5, 1])
Output:
    -1,7,6,3

Input:
solution.solution(5, [19, 14, 28])
Output:
    21,15,29

My Solution

This exercise should be quite simple if we first build the tree and then we find the location of the items in post order, however we can’t do that as h can be up to 30, giving us a total of 1073741824 nodes. So the solution is to evaluate each possible converter and calculating the values for the tree without generating it in full.

For that it is important to know how the tree should be built, perfect and post order, this 2 attributes gives us all we need.

def process_converter(max_idx, converter):
    prev_node = -1
    current_node = max_idx
    # The subtree is how many elements we have in total for a node
    subtree = max_idx

    if current_node == converter:
        return prev_node

    prev_node = current_node

    while subtree > 1:
        # As we go down through the tree, each level reduces the number by half, which is the same as shifting 1 bit
        subtree = subtree >> 1

        left = current_node - subtree - 1
        right = current_node - 1

        if converter == left or converter == right:
            return prev_node

        if converter < left:
            current_node = left
        elif converter > left:
            current_node = right

        prev_node = current_node

    return -1

def solution(h, q):
    max_idx = 2**h-1
    return [process_converter(max_idx, converter) for converter in q]

Juan Cruz Martinez

Juan has made it his mission to help aspiring developers unlock their full potential. With over two decades of hands-on programming experience, he understands the challenges and rewards of learning to code. By providing accessible and engaging educational content, Juan has cultivated a community of learners who share their passion for coding. Leveraging his expertise and empathetic teaching approach, Juan has successfully guided countless students on their journey to becoming skilled developers, transforming lives through the power of technology.