Ion Flux Relabeling

Origial Animation in CodePen.io

Created: Jan 16, 2023

Last modified: Oct 11, 2026

TL, DR.

Ion Flux Relabeling
===================

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.

Languages
=========

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

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

-- Java cases --
Input:
Solution.solution(5, {19, 14, 28})
Output:
    21,15,29

Input:
Solution.solution(3, {7, 3, 5, 1})
Output:
    -1,7,6,3

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

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

Commander Lambda's ion flux converter tree blew up, and a bunch of converters lost their labels. Luckily, we know how they were numbered: the tree is a perfect binary tree (every level completely full), and the labels came from a post-order traversal starting at 1. Given the height h and a list of labels, we need to return each one's parent, or -1 for the root.

The catch is that nobody hands you the tree, just numbers. So the whole challenge comes down to one question: what does a label tell us about where a node sits?

# Post-order in a nutshell

A post-order traversal visits the whole left subtree, then the whole right subtree, and only then the node itself. In other words, a node always gets its number after every one of its descendants. That gives us two handy facts:

The root comes last. A perfect tree of height $h$ has $2^h - 1$ nodes, so the root is always $2^h - 1$. For $h = 3$, that's 7.

Every subtree is a block of consecutive numbers, and its root is the biggest number in that block.

# Finding the children without drawing anything

Take a node labeled $v$ whose children head subtrees of height $n$. Right before $v$ got its label, we finished the right subtree, and the very last thing we labeled there was its root: the right child. So:

\text{right} = v - 1

To reach the left child, we just skip over the entire right subtree, which holds $2^n - 1$ nodes:

\text{left} = (v - 1) - (2^n - 1) = v - 2^n

Let's check it against the example tree. The root is 7 and its children have height 2, so the right one is $7 - 1 = 6$ and the left one is $7 - 4 = 3$. One level down the height is 1: the children of 3 are 2 and 1, and the children of 6 are 5 and 4. Exactly what the picture shows.

# Play with the tree

Pick a height and tap any converter to highlight it along with its parent. Keep an eye on the math below: what happens to the left children as you move up a level? What about the right ones?

4 is a left child and its subtree has height 1, so its parent sits 2^1 above it: 4 + 2 = 6.

# The code

My solution builds the whole tree top-down, one level at a time, writing down who each node's parent is along the way:

It starts with a dictionary data mapping every label to -1. The root is never overwritten, so it already holds the right answer.

prev_values keeps the nodes on the current level, starting with the root (1 << h) - 1, and n is the height of their children's subtrees.

For each node it works out both children with the formulas above: val1 = value - 1 is the right one and val2 = val1 - ((1 << n) - 1) the left one. Both get mapped to value and become the next level.

Once n hits 0 every leaf is in place, and answering each query is a plain dictionary lookup.

def solution(h, q):
    data = {i: -1 for i in range(1, (1 << h))}
    n = h-1
    prev_values = [(1 << h)-1]
    while n > 0:
        new_values = list()
        for value in prev_values:
            val1 = value - 1
            val2 = val1 - ((1 << n)-1)
            data[val1] = value
            data[val2] = value
            new_values.append(val1)
            new_values.append(val2)
        prev_values = new_values
        n = n - 1
    solution = []
    for val in q:
        solution.append(data.get(val, -1))
    return solution

# What if the tree is huge?

This approach is easy to follow and breezes through the test cases, but it has a hidden cost: it builds the entire tree, even if we only get asked about three nodes. That's $2^h - 1$ dictionary entries, and the statement allows $h = 30$: over a billion of them. On my machine $h = 22$ already takes about a second, and every extra level doubles both the time and the memory.

Bonus: finding the parent without building the tree

The same formulas work for walking down from the root in search of a single node. At each step we look at both children: if one of them is the label we want, the current node is its parent. If not, since every subtree is a block of consecutive numbers, anything smaller than the left child lives in the left subtree, and everything else in the right one.

def parent(h, label):
    node = (1 << h) - 1           # the root is always the last label
    if label == node:
        return -1
    n = h - 1                     # height of the children's subtrees
    while True:
        left, right = node - (1 << n), node - 1
        if label == left or label == right:
            return node
        # labels below the left child live in the left subtree
        node = left if label < left else right
        n -= 1


def solution(h, q):
    return [parent(h, label) for label in q]

That's at most $h$ steps per query and no extra memory: $O(h \cdot |q|)$ instead of $O(2^h)$. With $h = 30$ and 10,000 queries it finishes in a few hundredths of a second.

# Wrapping up

The trick here is noticing that in a perfect tree, a node's label already encodes where it lives. Once you know how big each subtree is, the rest is just arithmetic. Whenever a problem gives you numbers instead of a structure, it's worth asking what those numbers are trying to tell you.