Request for memory optimizations for solution to Google FooBar challenge, "ion_flux_relabeling,"
The problem description says:


  The domain of the integer \$h\$ is \$1 \le h \le 30\$


In the worst case, where \$h=30\$, the perfect tree has \$2^{31}-1 = 2147483647\$ nodes. And to store each node requires at least 32 bytes for the Tree object:

&gt;&gt;&gt; Tree().__sizeof__()
32


and a further 28 bytes for its data:

&gt;&gt;&gt; (123456).__sizeof__()
28


making at least 128 GB in all.

So this should clue you into the possibility that you might be able to compute the answer without building the tree. After all, the function you're being asked to write takes some numbers and returns some other numbers:

&gt;&gt;&gt; answer(7, [10, 25, 109])
[14, 29, 125]


so there might be some mathematical approach to computing the outputs based only on the numerical values of the inputs. (I won't spoil this for you by giving any more hints than that.)

This doesn't mean your work so far is wasted — as you try to figure out the mathematical approach, you can use the code you've written so far to check that the new code is producing the right answers.

(You didn't show us your original Haskell program, but I suspect it might have worked because Haskell's data structures are lazy — Haskell doesn't actually build them until just before they are needed. If you can figure out exactly which parts of the tree were being built in the Haskell version — and which were not — then maybe that will help you with your Python implementation.)