Постройка и обход Бинарного дерева, inorder postorder preorder.Ребята помогите ускорить код, система в тестах не принимает по лимиту времени(

Первая строка входных данных это число вершин в дереве, вторая это корень дерева и соответсвенно его дети ltft right, и последующие это вершины дерева и тоже с детьми left right, если -1 значит детей нету.вот пример входных и выходных данных

10-число вершин 0-это корень бинарного дерева у 0 левый ребенок это 7ая входная строчка(соответственно 70) и правый ребенок 2ая входная строчка соответственно 20, ну и так далее.. Sample Input:

10 0 7 2 10 -1 -1 20 -1 6 30 8 9 40 3 -1 50 -1 -1 60 1 -1 70 5 4 80 -1 -1 90 -1 -1

Sample Output:

50 70 80 30 90 40 0 20 10 60 0 70 50 40 30 80 90 20 60 10 50 80 90 30 40 70 10 60 20 0

Вот код, он рабочий но по времени не проходит, как его ускорить хз((

a = int(input())
doo = []
v = []
z = 1
for x in range(a):
    b = [int(x) for x in input().split()]
    if z == 1:
        doo.extend(['insert ' + str(b [0]) + " at root"])
    if b [1] != -1 and b [2] != -1:
        doo.extend(['insert ' + str(b [1]) + ' left ' + "of " + str(b [0])])
        doo.extend(['insert ' + str(b [2]) + ' right ' + "of " + str(b [0])])
    elif b [1] != -1 and b [2] == -1:
        doo.extend(['insert ' + str(b [1]) + ' left ' + "of " + str(b [0])])
    elif b [1] == -1 and b [2] != -1:
        doo.extend(['insert ' + str(b [2]) + ' right ' + "of " + str(b [0])])
    v.append(b [0])
    z += 1


class BinaryTree:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None

    def set_root(self, key):
        self.key = key

    def insert_left(self, new_node):
        self.left = new_node

    def insert_right(self, new_node):
        self.right = new_node



    def search(self, key):
        if self.key == key:
            return self
        if self.left is not None:
            temp = self.left.search(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp = self.right.search(key)
            return temp
        return None



btree = None

k = 1
for do in doo:
    operation = do.split() [0]
    if operation == 'insert':
        if k == 1:
            data = int(do.split() [1])
            k += 1
        else:
            data = v [int(do.split() [1])]
        new_node = BinaryTree(data)
        suboperation = do.split() [2]
        if suboperation == 'at':
            btree = new_node
        else:
            position = do.split() [4]
            key = int(position)
            ref_node = None
            if btree is not None:
                ref_node = btree.search(key)
            if ref_node is None:
                doo.extend([do])
                continue
            if suboperation == 'left':
                ref_node.insert_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_right(new_node)


def Preorder(btree) :
    if btree:
        print(btree.key,end=" ")    
        Preorder(btree.left) 
        Preorder(btree.right) 

def Inorder(btree): 
        if btree: 
            Inorder(btree.left) 
            print(btree.key,end=" ")
            Inorder(btree.right)  


def Postorder(btree) :
    if btree :
        Postorder(btree.left) 
        Postorder(btree.right)
        print(btree.key,end=" ")               


Inorder(btree) 
print()
Preorder(btree) 
print()
Postorder(btree)