Request for memory optimizations for solution to Google FooBar challenge, "ion_flux_relabeling," I just finished one of the Google FooBar Challenges.My Python is super rusty. I did the challenge in Haskell first and then attempted to covert the code. I am guessing that led to some bad Python Practices. 


  Oh no! Commander Lambda's latest experiment to improve the efficiency
  of her LAMBCHOP doomsday device has backfired spectacularly. She 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. She's 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, she 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 answer(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, answer(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 &lt;= h &lt;= 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.


How could I make my solution more memory efficient? 

def splitInHalf(aList):
    full = len(aList)
    half = full/2
    return aList[0:half], aList[half:full]

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None
    def __str__(self):
        return ("Data = " + str(self.data) + "Left = " + str(self.left) + "Right = " + str(self.right)  )

def makeTree(h):
    limit = (2**h)-1
    fluxConverters = list(range(limit,0,-1))
    result = generate_tree(list(fluxConverters))
    return result

def generate_tree(listInt):
    if not listInt:
        return None
    elif (len(listInt) == 1):
        rTreeOne = Tree()
        rTreeOne.data = listInt[0]
        return rTreeOne
    else:
        rTreeList = Tree()
        rTreeList.data   = listInt.pop(0)
        half1, half2 = splitInHalf(list(listInt))
        rTreeList.left   = generate_tree(half1)
        rTreeList.right  = generate_tree(half2)
        return rTreeList

def searchTree(tree,search):
    if tree == None:
        return -1
    else:
        if (nextHaz(tree.left,search) | nextHaz(tree.right,search)):
            return tree.data
        else:
            left = searchTree(tree.left,search)
            right = searchTree(tree.right,search)
            return mergeResults(left,right)

def mergeResults(x,y):
    if(x!=-1):
        return x
    else:
        return y

def nextHaz(tree, search):
    if(tree != None):
        return tree.data == search
    else:
        return False

def answer(h,q):
    tree = makeTree(h)
    partialSearch = lambda x : searchTree(tree,x)
    result = map(partialSearch,q)
    return result

answer(3,[7, 3, 5, 1])
testOneResult = [-1, 7, 6, 3]

answer(5,[19, 14, 28])
testTwoResult = [21, 15, 29]
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.)