Binary Tree V2

btree2.py

class btree:
    def __init__(self, h):
        self.height = h
        self.node_count = btree.calc_node_count(h)
        self.head = None
        self.index = 1
        self.found = []
        
    @staticmethod
    def get_midpoints(x, y):
        #find mid point, exit if at terminal node
        #When left and right are the same terminal nodes have been reached
        if (x == y):
            return (x, None, None)
        
        mp = int((y-x)/2 + x)
        left = (x, mp - 1)
        right = (mp + 1, y)
        
        values = (mp, left, right)

        return values

    @staticmethod
    def calc_node_count(height = 0):
        count = 0
        total = 0
        for x in range(height):
            if (x == 0):
                count = 1
            else:
                count = count * 2

            total += count

        return total
    
    @staticmethod
    def create_leaf(value):
        return {
            'l': None,
            'r': None,
            'v': value,
            'x': None
        }
    
    def build(self):
        mp = btree.get_midpoints(1, self.node_count)
        self.head = btree.create_leaf(mp[0])
        
        self.add(mp[1], self.head)
        self.add(mp[2], self.head)
    
    def add(self, values, node):
        mp = btree.get_midpoints(values[0], values[1])
        child = btree.create_leaf(mp[0])
        
        if mp[0] < node['v']:
                node['l'] = child
        else:
            node['r'] = child
            
        #stop recursing at terminal nodes
        if(mp[1] != None):
            self.add(mp[1], child)
        if mp[2] != None:
            self.add(mp[2], child)
            
    def label_post_order(self, node):
        if (node != None):
            self.label_post_order(node['l'])
            self.label_post_order(node['r'])
            node['x'] = self.index
            self.index += 1
            
    def find(self, node, value):
        if (node != None):
            if node['x'] == value:
                self.found.append(-1)
                return
            if node['l']:
                if node['l']['x'] == value:
                    self.found.append(node['x'])
                    return
            
            if node['r']:
                if node['r']['x'] == value:
                    self.found.append(node['x'])
                    return
                    
            self.find(node['l'], value)
            self.find(node['r'], value)
            
            
def answer(h, q):
    bt = btree(h)
    bt.build()
    bt.label_post_order(bt.head)
    
    for x in q:
        bt.find(bt.head, x)
        
    return bt.found