perfect_binary_tree.py

# Solution 2.2 of foo.bar

def solution(h, q):
    
    # We'll use a dictionary to hold the 
    # solutions so that we can store as
    # q[x] = soln and later return back
    # in order, regardless of how our 
    # algorithm iterates through the tree. 
    solutions = {} 
    
    # h is the height of the tree
    # q is a [int] 
    # return [int]

    # Calculate the total nodes for a perfect binary tree.
    n = 2**h - 1

    # Start at max node. 
    node = n
 
    # Get the recursion started here. 
    solutions, added, lastnode = addNode(node, h, 1, q, solutions)
    
    # Ensure that we account for the max node being part of q.
    for x in added:
        if x in q:
            solutions[x] = -1

    # Process solutions. 
    solns = []
    for x in q:
        if x in solutions:
            solns.append(solutions[x])
        else:
            solns.append(-1)

    return solns
    

def addNode(node, maxh, currentH, q, solutions):
    
    # The nodes on this level/side of the tree (2 max).
    currAdded = []
    
    # The current node we're on. 
    currNode = node

    # We'll iterate through the two nodes 
    # on this level on this side of the tree. 
    while len(currAdded) < 2:
        
        currAdded.append(currNode)
        currNode -= 1

        # If this is not the bottom of the tree, we'll want to iterate deeper. 
        if currentH < maxh:
            
            solutions, added, node = addNode(currNode, maxh, currentH+1, q, solutions)
            
            # Capture any values that we're looking for,
            # as the level we're currently on has the solution. 
            for x in range(len(added)):
                
                # If we find it, we'll add it to the solution dictionary. 
                if added[x] in q:
                    solutions[added[x]] = currNode + 1
            
            # Account for the node changing while we were recursing. 
            currNode = node
            
        # The top level of the tree only has a single node. 
        if currentH == 1:
            return solutions, currAdded, currNode

    

    return solutions, currAdded, currNode

solution(3, [7, 3, 5, 1]) # [-1,7,6,3]
solution(5, [19, 14, 28]) # [21,15,29]