# 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

global node_list
global solution
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:

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.

• Wouldn't the parent of 3 be 7 in your example, rather than 6? Sep 16, 2017 at 14:41
• @AustinHastings yeah sorry that was a typo Sep 16, 2017 at 14:42
• What are the limits on h and q? Sep 16, 2017 at 14:43
• @AustinHastings 1<=h<=30 and 1<=q<=10,000 unique elements Sep 16, 2017 at 14:45

The problem of "what is the parent of one node in the tree" can be solved as a recurrence relation, either using arithmetic or using the bits in the binary representation of the number.

The problem of "what are the various parents of many nodes in the tree" is a group solution that cries out for some batch computation followed by speed-oriented lookups.

Look at the numeric properties of the nodes. You should not be computing a tree for this.

Also, look at the desired problem solution: you want to perform a computation or lookup for each number in a list. Thus, your information storage should be optimized for this.

Given that your tree represents a range of numbers, I'll suggest either a dictionary or a list. Since the numbers are a dense group of integers that start from 1, I'll suggest a list.

Parents = [0] * (n+1)


Given h, how can you predict n (above)? What's the number at the root of the tree?

Given R the number at the root of a tree, what are the values of the numbers at the root of the next lower subtrees? (Hint: easy for the left, harder for the right.)