Problem:

  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Binary Search Tree I

 Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue. 

  Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:

 Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $x.key \leq y.key$.

  The following figure shows an example of the binary search tree.

  For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk.

  A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively.

  To insert a new value $v$ into a binary search tree $T$, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node $z$ for which $z.key = v$, $z.left = NIL$, and $z.right = NIL$. The procedure modifies $T$ and some of the fields of $z$ in such a way that $z$ is inserted into an appropriate position in the tree.

1 insert(T, z)
2     y = NIL // parent of x
3     x = 'the root of T'
4     while x &ne; NIL
5         y = x // set the parent
6         if z.key < x.key
7             x = x.left // move to the left child
8         else 
9             x = x.right // move to the right child
10    z.p = y
11
12    if y == NIL // T is empty
13        'the root of T' = z
14    else if z.key < y.key
15        y.left = z // z is the left child of y
16    else 
17        y.right = z // z is the right child of y

  Write a program which performs the following operations to a binary search tree $T$.

insert  $k$: Insert a node containing $k$ as key into $T$.

print: Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.

  You should use the above pseudo code to implement the insert operation. $T$ is empty at the initial state.

Input

  In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$ or print are given.

Output

  For each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.

Constraints

The number of operations $\leq 500,000$

The number of print operations $\leq 10$.

$-2,000,000,000 \leq key \leq 2,000,000,000$

The height of the binary tree does not exceed 100 if you employ the above pseudo code.

The keys in the binary search tree are all different.

Sample Input 1

8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

Sample Output 1

 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print


Sample output:
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
    
    def insert(node, x):
        if node == None:
            return Node(x)
        elif x == node.data:
            return node
        elif x < node.data:
            node.left = Node.insert(node.left, x)
        else:
            node.right = Node.insert(node.right, x)
        return node
    
    def find(node, x):
        if node.data == x:
            return True
        elif node.left != None and node.data > x:
            return Node.find(node.left, x)
        elif node.right != None and node.data < x:
            return Node.find(node.right, x)
        else:
            return False
        
    def delete(node, x):
        if node.data == x:
            if (node.left == None) and (node.right == None):
                return None
            elif node.left == None:
                return node.right
            elif node.right == None:
                return node.left
            else:
                #????????????
                node.data = Node.serch_min(node.right)
                node.right = Node.delete_min(node.right)
                return node
        elif node.data > x:
            node.left =  Node.delete(node.left, x)
        else:
            node.right = Node.delete(node.right, x)
        return node
        
    def serch_min(node):
        if node.left != None:
            return Node.serch_min(node.left)
        else:
            return node.data
    
    def delete_min(node):
        if node.left == None:
            return node.right
        else:
            node.left = Node.delete_min(node.left)
            return node    
        
    def inorder_print(node):
        if node.left != None:
            Node.inorder_print(node.left)
        print("",node.data,  end="")
        if node.right != None:
            Node.inorder_print(node.right)
    def preorder_print(node):
        print("",node.data,  end="")
        if node.left != None:
            Node.preorder_print(node.left)
        if node.right != None:
            Node.preorder_print(node.right)
        
class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        self.root = Node.insert(self.root, x)

    def find(self, x):
        if Node.find(self.root, x):
            print("yes")
        else:
            print("no")
            
    def delete(self, x):
        self.root = Node.delete(self.root, x)
        
    def print_tree(self):
        Node.inorder_print(self.root)
        print()
        Node.preorder_print(self.root)
        print()

def main():
    T = BinaryTree()
    m = int(sys.stdin.readline())
    for i in range(m):
        s = sys.stdin.readline().strip()
        if(s == "print"):
            T.print_tree()
        elif s.split()[0] == "find":
            T.find(int(s.split()[1]))
        elif s.split()[0] == "delete":
            T.delete(int(s.split()[1]))
        else:
            z = int(s.split()[1])
            T.insert(z)
        #print(s)
        #T.print_tree()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
    
    def insert(node, x):
        if node == None:
            return Node(x)
#==============================================================================
#         elif x == node.data:
#             return node
#==============================================================================
        elif x < node.data:
            node.left = Node.insert(node.left, x)
        else:
            node.right = Node.insert(node.right, x)
        return node
    
    def find(node, x):
        if node.data == x:
            return True
        elif node.left != None and node.data > x:
            return Node.find(node.left, x)
        elif node.right != None and node.data < x:
            return Node.find(node.right, x)
        else:
            return False
        
    def delete(node, x):
        if node.data == x:
            if (node.left == None) and (node.right == None):
                return None
            elif node.left == None:
                return node.right
            elif node.right == None:
                return node.left
            else:
                #????????????
                node.data = Node.serch_min(node.right)
                node.right = Node.delete_min(node.right)
                return node
        elif node.data > x:
            node.left =  Node.delete(node.left, x)
        else:
            node.right = Node.delete(node.right, x)
        return node
        
    def serch_min(node):
        if node.left != None:
            return Node.serch_min(node.left)
        else:
            return node.data
    
    def delete_min(node):
        if node.left == None:
            return node.right
        else:
            node.left = Node.delete_min(node.left)
            return node    
        
    def inorder_print(node):
        if node.left != None:
            Node.inorder_print(node.left)
        print("",node.data,  end="")
        if node.right != None:
            Node.inorder_print(node.right)
    def preorder_print(node):
        print("",node.data,  end="")
        if node.left != None:
            Node.preorder_print(node.left)
        if node.right != None:
            Node.preorder_print(node.right)
        
class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        self.root = Node.insert(self.root, x)

    def find(self, x):
        if Node.find(self.root, x):
            print("yes")
        else:
            print("no")
            
    def delete(self, x):
        self.root = Node.delete(self.root, x)
        
    def print_tree(self):
        Node.inorder_print(self.root)
        print()
        Node.preorder_print(self.root)
        print()

def main():
    T = BinaryTree()
    m = int(sys.stdin.readline())
    for i in range(m):
        s = sys.stdin.readline().strip()
        if(s == "print"):
            T.print_tree()
        elif s.split()[0] == "find":
            T.find(int(s.split()[1]))
        elif s.split()[0] == "delete":
            T.delete(int(s.split()[1]))
        else:
            z = int(s.split()[1])
            T.insert(z)
        #print(s)
        #T.print_tree()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self, id, left=-1, right=-1, parent=-1):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent  
    def show(self):
        print 'node %d: parent = %d, left = %d, right = %d' % (self.id, self.parent, self.left, self.right)

class Stack():
    def __init__(self):
        self.el = []
    def add(self, el):
        self.el.append(el)
    def pop(self):
        return self.el.pop()

def insert(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while x != None:
            y = x
            if z.id < x.id:
                if x.left == -1:
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    break
                x = T[x.right]
        z.parent = x.id
    if y == None:
        rootId = z.id
    elif z.id < y.id:
        y.left = z.id
    else:
        y.right = z.id
    T[z.id] = z
    return T

def printOrder(T):
    ### inorder ###
    global rootId
    pos = rootId
    st = Stack()
    ans = []
    while True:
        if T[pos].left != -1 and T[pos].left not in ans:
            if T[pos].right != -1:
                st.add(T[pos].right)
            st.add(pos)
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1 and T[pos].right not in ans:
            ans.append(pos)
            pos = T[pos].right
        else:
            ans.append(pos)
            if len(ans) == len(T):
                break
            pos = st.pop()    
    print '', ' '.join(map(str, ans))

    ### preorder ###
    pos = rootId
    st = Stack()
    ans = []
    while True:
        ans.append(pos)
        if len(ans) == len(T):
            break
        if T[pos].left != -1 and T[pos].right != -1:
            st.add(T[pos].right)
        if T[pos].left != -1:
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1:
            pos = T[pos].right
        else:
            pos = st.pop()
    print '', ' '.join(map(str, ans))


### input ###
T = {}
a = []
n = int(raw_input())
rootId = None
for i in range(n):
    tmp = raw_input().split()
    if tmp[0] == 'insert':
        T[int(tmp[1])] = Node(int(tmp[1]))
        T = insert(T, Node(int(tmp[1])))
    elif tmp[0] == 'print':
        printOrder(T)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)

def insert(k, node):
    if k < node:
        if tree[node]["left"] == -1:
            tree[node]["left"] = k
            tree[k] = {"parent": node, "left": -1, "right": -1}
            return
        else:
            insert(k, tree[node]["left"])
    else:
        if tree[node]["right"] == -1:
            tree[node]["right"] = k
            tree[k] = {"parent": node, "left": -1, "right": -1}
            return
        else:
            insert(k, tree[node]["right"])


def pre_order(n):
    global pre_text
    
    if n == -1:
        return
    pre_text += " {}".format(n)
    pre_order(tree[n]["left"])
    pre_order(tree[n]["right"])


def in_order(n):
    global in_text
    
    if n == -1:
        return

    in_order(tree[n]["left"])
    in_text += " {}".format(n)
    in_order(tree[n]["right"])   

M = int(input())
root = "nan"
while root == "nan":
    inp = [n for n in input().split()]
    if inp[0] == "print":
        print()
        print()
    else:
        root = int(inp[1])

tree = {root:{"parent": -1, "left": -1, "right": -1}}

for _ in range(M-1):
    inp = [n for n in input().split()]
    if inp[0] == "print":
        in_text = ""
        pre_text = ""
        in_order(root)
        pre_order(root)
        print(in_text[:])
        print(pre_text[:])
    else:
        insert(int(inp[1]), root)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)

def insert(k, node):
    if k < node:
        if tree[node]["left"] == None:
            tree[node]["left"] = k
            tree[k] = {"parent": node, "left": None, "right": None}
            return
        else:
            insert(k, tree[node]["left"])
    else:
        if tree[node]["right"] == None:
            tree[node]["right"] = k
            tree[k] = {"parent": node, "left": None, "right": None}
            return
        else:
            insert(k, tree[node]["right"])


def pre_order(n):
    global pre_text
    
    if n == None:
        return
    pre_text += " {}".format(n)
    pre_order(tree[n]["left"])
    pre_order(tree[n]["right"])


def in_order(n):
    global in_text
    
    if n == None:
        return

    in_order(tree[n]["left"])
    in_text += " {}".format(n)
    in_order(tree[n]["right"])   

M = int(input())
root = "nan"
while root == "nan":
    inp = [n for n in input().split()]
    if inp[0] == "print":
        print()
        print()
    else:
        root = int(inp[1])

tree = {root:{"parent": None, "left": None, "right": None}}

for i, _ in enumerate(range(M-1)):
    inp = [n for n in input().split()]
    if inp[0] == "print":
        in_text = ""
        pre_text = ""
        in_order(root)
        pre_order(root)
        print(in_text[:])
        print(pre_text[:])
    else:
        insert(int(inp[1]), root)
        #if i%1000 == 0:
        #    print("done {}/{}".format(i, M))

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self,x):
        if self.root == None:
            self.root = Node(x)
        cur = self.root
        while True:
            if cur.value > x:
                if cur.left == None:
                    cur.left = Node(x)
                    break
                cur = cur.left
            elif cur.value < x:
                if cur.right == None:
                    cur.right = Node(x)
                    break
                cur = cur.right
            else:
                break

    def mprint(self):
        print '',
        print ' '.join(map(str, self.inorder(self.root)))
        print '',
        print ' '.join(map(str, self.preorder(self.root)))

    def inorder(self, cur):
        ret = []
        if cur.left != None:
            ret += self.inorder(cur.left)
        ret.append(cur.value)
        if cur.right != None:
            ret += self.inorder(cur.right)
        return ret

    def preorder(self, cur):
        ret = []
        ret.append(cur.value)
        if cur.left != None:
            ret += self.preorder(cur.left)
        if cur.right != None:
            ret += self.preorder(cur.right)
        return ret



m = int(raw_input())
tree = BST()
for _ in range(m):
    line = raw_input()
    if line[0] == 'i':
        num = int(line.split(' ')[1])
        tree.insert(num)
    elif line[0] == 'p':
        tree.mprint()
    else:
        raise Exception("Unknown command")

Submission status: Time Limit Exceeded

Solution code:
# Binary Search Tree
class Node:
    def __init__(self, v):
        self.value = v
        self.parent = None
        self.left = None
        self.right = None

# 木の根を引数として受け取り，データを挿入した新しい木の根を返す
def insert(node, x):
    if node is None:
        return Node(x)
    elif x == node.value:
        return node
    elif x < node.value:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

def preorder_walk(node):
    if node:
        yield node.value
        for x in preorder_walk(node.left):
            yield x
        for x in preorder_walk(node.right):
            yield x

def inorder_walk(node):
    if node:
        for x in inorder_walk(node.left):
            yield x
        yield node.value
        for x in inorder_walk(node.right):
            yield x

root = None
n = int(input())
for i in range(n):
    cmd, *val = input().split()
    if cmd == "insert":
        root = insert(root, int(val[0]))
    elif cmd == "print":
        print("", *inorder_walk(root))
        print("", *preorder_walk(root))

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

class BinarySearchTree():
    def __init__(self, n):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = n

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val, parent=y)

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        preordered = []
        self.init_color()
        def preorder_bfs(s):
            preordered.append(self.nodes[s].val)
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        return preordered

    def inorder(self):
        inordered = []
        self.init_color()

        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            inordered.append(self.nodes[u].val)
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        return inordered

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

m = int(input())
bst = BinarySearchTree(m)
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val, parent=y)

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

    def find(self, val):
        x = self.root
        while x != None:
            if self.nodes[x].val == val:
                return True
            elif self.nodes[x].val < val:
                x = self.nodes[x].right
            else:
                x = self.nodes[x].left
        return False

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        preordered = []
        self.init_color()
        def preorder_bfs(s):
            preordered.append(self.nodes[s].val)
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        return preordered

    def inorder(self):
        inordered = []
        self.init_color()

        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            inordered.append(self.nodes[u].val)
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        return inordered

def print_elements(ordered):
    print(' ', end='')
    print(' '.join(list(map(str, ordered))))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
        continue
    ope, num = op.split(' ')
    num = int(num)
    if ope == 'insert':
        bst.insert(num)
    elif ope == 'find':
        if bst.find(num):
            print('yes')
        else:
            print('no')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

class BinarySearchTree():
    def __init__(self, n):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = n

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val, parent=y)

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        preordered = []
        self.init_color()
        def preorder_bfs(s):
            preordered.append(self.nodes[s].val)
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        return preordered

    def inorder(self):
        inordered = []
        self.init_color()

        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            inordered.append(self.nodes[u].val)
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        return inordered

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

m = int(input())
bst = BinarySearchTree(m)
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

class BinarySearchTree():
    def __init__(self, n):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = n

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val, parent=y)

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        self.init_color()
        def preorder_bfs(s):
            print('', self.nodes[s].val, end='')
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        print('')

    def inorder(self):
        self.init_color()

        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            print('', self.nodes[u].val, end='')
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        print('')

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

m = int(input())
bst = BinarySearchTree(m)
for i in range(m):
    op = input()
    if op == 'print':
        bst.inorder()
        bst.preorder()
    else:
        num = int(op[7:])
        bst.insert(num)