0
\$\begingroup\$

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.

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

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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.