Generating and finding parent nodes in a post-order tree

Given a height h and list q of integers, list the parent node of each element in q, if nodes are read in post-order sequence starting at 1. The tree could be read like this if h=3.

    7
  3   6
 1 2 4 5

If h = 3 and q = [1,3,7] the output would be the list [3, 6, -1] where the parent of the root is always -1.

How can I make this code faster? It does okay until h=10, then it slows down since it has to check \$2^h-1\$ nodes.

#Generate a perfect binary tree of height h
#Find the parent nodes of the values in list g, return negative 1 for the 
#root

node_list = []
solution = {}

class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None
        self.parent = -1
        self.left_edge = True
        self.depth = 0


def answer(h, q):
    global node_list
    global solution
    final_answer = []
    root = int(pow(2, h))-1
    solution.update({root: -1})
    node_list = (list(range(root+1)))
    node_list.reverse()
    node_list.pop()
    node = Node()
    node.data = root
    node.left = left_branch(h, node)
    node.right = right_branch(h, node)
    for i in q:
        for key in solution:
            if i == key:
                final_answer.append(solution[key])
        return final_answer


def left_branch(h, parent: Node):
    global node_list
    global solution
    new_node = Node()
    new_node.depth = parent.depth + 1
    new_node.parent = parent.data

    try:
        if parent.left_edge:
            new_node.data = parent.data//2
        node_list.remove(new_node.data)
    else:
        new_node.left_edge = False
        new_node.data = parent.data - int(pow(2, h - new_node.depth))
        print(new_node.data)
        node_list.remove(new_node.data)

    except ValueError:
        if not(new_node.data in node_list):
            return new_node

    solution.update({new_node.data: parent.data})
    left = left_branch(h, new_node)
    right = right_branch(h, new_node)
    new_node.left = left
    new_node.right = right
    return new_node


def right_branch(h, parent: Node):
    global node_list
    global solution
    new_node = Node()
    new_node.left_edge = False
    new_node.depth = parent.depth + 1
    new_node.parent = parent.data
    new_node.data = parent.data - 1
    try:
        node_list.remove(new_node.data)
    except ValueError:
        return new_node
    left = left_branch(h, new_node)
    right = right_branch(h, new_node)
    new_node.left = left.data
    new_node.right = right.data

    solution.update({new_node.data: parent.data})

    return new_node

This was a challenge given by Google Foobar. The time window has expired. My code took too long to run. I'm wondering about the optimal way to solve this problem.