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: Accepted

Solution code:
import sys

sys.setrecursionlimit(2 ** 20)  # 再帰回数上限の向上 かなり多くしないとREになる


class Node:
    def __init__(self,
                 left,
                 right):
        self.left = left
        self.right = right


def insert(t: dict, i: int, r: int):
    if r > i:
        if t[r].left is not None:
            insert(t, i, t[r].left)
        else:
            t[r].left = i
    if r < i:
        if t[r].right is not None:
            insert(t, i, t[r].right)
        else:
            t[r].right = i


def inorder(t: dict, p: int, in_ls: list):
    if t[p].left is not None:
        inorder(t, t[p].left, in_ls)
    in_ls.append(p)
    if t[p].right is not None:
        inorder(t, t[p].right, in_ls)


def preorder(t: dict, p: int, pre_ls: list):
    pre_ls.append(p)
    if t[p].left is not None:
        preorder(t, t[p].left, pre_ls)
    if t[p].right is not None:
        preorder(t, t[p].right, pre_ls)


N = int(input())
T = {}
in_list = []
pre_list = []

order = list(map(str, input().split()))
root = int(order[1])
T[root] = Node(None, None)

for _ in range(N-1):
    order = str(input())
    if order[0] == 'i':
        order = list(order.split())
        T[int(order[1])] = Node(None, None)
        insert(T, int(order[1]), root)
    else:
        inorder(T, root, in_list)
        print('', *in_list)
        preorder(T, root, pre_list)
        print('', *pre_list)
        in_list = []
        pre_list = []

Submission status: Accepted

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

    def insert(self, z):
        z = Node(z)
        self.nodes.append(z)
        y = None
        x = self.root
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
            z.parent = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    
    def dfs(self, node):
        self.preorder.append(node.key)
        if node.left is not None:
            self.dfs(node.left)

        self.inorder.append(node.key)

        if node.right is not None:
            self.dfs(node.right)

    def out(self):
        self.preorder = []
        self.inorder = []
        self.dfs(self.root)

        print("", *self.inorder)
        print("", *self.preorder)


class Node:
    def __init__(self, v):
        self.key = v
        self.left = None
        self.right = None
        self.parent = None


def main():
    global preorder
    global inorder
    preorder = []
    inorder = []
    T = BinarySearchTree()
    n = int(input())
    for i in range(n):
        command = input().split()
        if command[0] == "print":
            T.out()
        else:
            T.insert(int(command[1]))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
NIL = -1
class Node():
    def __init__(self, val):
        self.val = val
        self.parent = NIL
        self.left = NIL
        self.right = NIL
    def __str__(self):
        return "val:{}, parent:{}, left:{}, right:{}".format(self.val, self.parent, self.left, self.right)
        
class Tree():
    def __init__(self):
        self.Nodes = {}
        self.Nodes[NIL] = Node(NIL)
        self.root = self.Nodes[NIL]
        
    def insert(self, node):
        y = self.Nodes[NIL]
        x = self.root
        while x.val != NIL:
            y = x
            if(node.val < x.val):
                x = self.Nodes[x.left]
            else:
                x = self.Nodes[x.right]
        node.parent = y.val
        
        if(y.val == NIL):
            self.root = node
        elif(node.val < y.val):
            y.left = node.val
        else:
            y.right = node.val
        self.Nodes[node.val] = node

    def getPreOrder(self):
        return self.preParse(self.root.val, [])    
        
    def getInOrder(self):
        return self.inParse(self.root.val, [])
    
    def getPostOrder(self):
        return self.postParse(self.root.val, [])
        
    def inParse(self, u, res):
        if(u == NIL):
            return
        self.inParse(self.Nodes[u].left, res)
        res += [u]
        self.inParse(self.Nodes[u].right, res)
        return res

    def postParse(self, u, res):
        if(u == NIL):
            return
        self.postParse(self.Nodes[u].left, res)
        self.postParse(self.Nodes[u].right, res)
        res += [u]
        return res
    
    def preParse(self, u, res):
        if(u == NIL):
            return 
        res += [u]
        self.preParse(self.Nodes[u].left, res)
        self.preParse(self.Nodes[u].right, res)
        return res
        
n = int(input())

tree = Tree()
for row in range(n):
    operate = input().split()
    if(operate[0] == "insert"):
        tree.insert(Node(int(operate[1])))
        
    if(operate[0] == "print"):
        print(" {}".format( " ".join([str(ss) for ss in tree.getInOrder()])))
        print(" {}".format( " ".join([str(ss) for ss in tree.getPreOrder()])))

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None


root = None

def insert(key):
    global root
    x = root #Tの根
    y = None #親を設定
    # while x: x, y = x.left if key < x.key else x.right, x
    while x is not None:
        y = x
        if key < x.key:
            x = x.left #左の子へ移動
        else:
            x = x.right  #右の子へ移動

    if y is None: #Tが空の場合
        root = Node(key)
    elif key < y.key:
        y.left = Node(key) #keyをyの左の子にする
    else:
        y.right = Node(key) #keyをyの右の子にする

def inorder(node):
    return   inorder(node.left) + " "+ str(node.key) + inorder(node.right) if node else ''
def preorder(node):
    return   " " + str(node.key) + preorder(node.left) + preorder(node.right) if node else ''
input()
for e in sys.stdin:
    if e[0] == "i":
        insert(int(e[7:]))
    else:
        print(inorder(root))
        print(preorder(root))

Submission status: Accepted

Solution code:

import sys



# ---------------------------------------------------
# ---------------------------------------------------
# ---------------------------------------------------



def resolve():
    class Node:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

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

        def insert(self, data):
            if self.node is None:
                self.node = Node(data)
            else:
                self._insert(data, self.node)

        def _insert(self,data, cur_node):
            if data < cur_node.data:
                if cur_node.left is None:
                    cur_node.left = Node(data)
                else:
                    self._insert(data, cur_node.left)
            elif data > cur_node.data:
                if cur_node.right is None:
                    cur_node.right = Node(data)
                else:
                    self._insert(data, cur_node.right)
            else:
                print("同じ値があります。")

        def pre_order_print(self):
            if self.node:
                self._pre_order_print(self.node)

        def _pre_order_print(self, cur_node):
            if cur_node:
                print(" ", end="")
                print(cur_node.data, end="")
                self._pre_order_print(cur_node.left)
                self._pre_order_print(cur_node.right)

        def in_order_print(self):
            if self.node:
                self._in_order_print(self.node)

        def _in_order_print(self, cur_node):
            if cur_node:
                self._in_order_print(cur_node.left)
                print(" ", end="")
                print(cur_node.data, end="")
                self._in_order_print(cur_node.right)

    N = int(input())
    bst = BST()
    lines = sys.stdin.readlines()
    for line in lines:
        s = line.split()
        if s[0] == "insert":
            x = int(s[1])
            bst.insert(x)
        else:
            # 出力規定： 先頭に1つの空白もいれる
            bst.in_order_print()
            print()
            bst.pre_order_print()
            print()


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
INFTY=2000000000+1

class Node:
    def __init__(self,key=INFTY):
        self.key=key
        self.parent=-1
        self.left=-1
        self.right=-1

root=-1
T=[]
commands=[]
preorderList=[]
inorderList=[]

def readinput():
    global commands

    n=int(input())
    for _ in range(n):
        s=input().split()
        command=s[0]
        if(len(s)>1):
            op=s[1]
        commands.append((command,int(op)))

def insert(op):
    global T
    global root

    #print('[{}]'.format(op))
    zidx=len(T)
    z=Node(op)
    T.append(z)

    yidx=-1
    xidx=root
    while(xidx != -1):
        x=T[xidx]
        yidx=xidx
        if(z.key<x.key):
            xidx=x.left
            #print('left: {} < {}'.format(z.key, x.key))
        else:
            xidx=x.right
            #print('right')
    z.parent=yidx

    if yidx==-1:
        root=zidx
        #print('root changed')
    elif z.key<T[yidx].key:
        T[yidx].left=zidx
    else:
        T[yidx].right=zidx

def getPreorderList(id):
    global preorderList

    preorderList.append(id)
    node=T[id]
    if(node.left!=-1):
        getPreorderList(node.left)
    if(node.right!=-1):
        getPreorderList(node.right)

def getInorderList(id):
    global inorderList

    node=T[id]
    if(node.left!=-1):
        getInorderList(node.left)
    inorderList.append(id)
    if(node.right!=-1):
        getInorderList(node.right)

def printPreorderList():
    for i in preorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printInorderList():
    for i in inorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printT():
    global inorderList
    global preorderList

    inorderList=[]
    preorderList=[]
    
    getInorderList(root)
    printInorderList()
    getPreorderList(root)
    printPreorderList()
    #for node in T:
    #    print(node.key, node.parent, node.left, node.right)    

def main():
    global commands

    for command,op in commands:
        if(command=='insert'):
            insert(op)
        elif(command=='print'):
            printT()

if __name__=='__main__':
    readinput()
    main()

Submission status: Accepted

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

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

    def insert(self, data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while True:
                entry = n.key_value
                if data < entry:
                    if n.left is None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif data > entry:
                    if n.right is None:
                        n.right = Node(data)
                        return
                    n = n.right
                else:
                    n.data = data
                    return

    def inorder(self,node):
        if node is None:
            return
        else:
            self.inorder(node.left)
            print(' {}'.format(node.key_value),end='')
            self.inorder(node.right)

    def preorder(self,node):
        if node is None:
            return
        else:
            print(' {}'.format(node.key_value),end='')
            self.preorder(node.left)
            self.preorder(node.right)

if __name__ == "__main__":
    n = int(input())

    bst = BST()
    for i in range(n):
        o = input().split()

        if o[0] == 'insert':
            bst.insert(int(o[1]))
        elif o[0] == 'print':
            bst.inorder(bst.root)
            print()
            bst.preorder(bst.root)
            print()

Submission status: Accepted

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

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

    def insert(self, z:Node):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.p = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

def Preorder(target:Node):
    yield target.key
    if target.left != None:
        yield from Preorder(target.left)
    if target.right != None:
        yield from Preorder(target.right)

def Inorder(target:Node):
    if target.left != None:
        yield from Inorder(target.left)
    yield target.key
    if target.right != None:
        yield from Inorder(target.right)

from sys import stdin
tree = Tree()
n = int(input())
lines = stdin.readlines()
for line in lines:
    proc,*key = line.split()
    if proc == "insert":
        tree.insert(Node(int(key[0])))
    else:
        print(" ",end="")
        print(*Inorder(tree.root))
        print(" ",end="")
        print(*Preorder(tree.root))

Submission status: Accepted

Solution code:
import sys

class Node():
    #key = ตัว z เอง และตัวด้านซ้ายด้านขวา
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left, self.right = None, None
        
    def __str__(self):
        return self.key

root = None
#z คือรับเลขเข้ามาว่าจะ insert ค่าไหน
def insert(z):
    global root
    x, y = root, None
    #ทำการ update ค่า y ว่าตัวไหนเป็น root ต่อไป โดยมาเทียบกับ root ว่าจะลงซ้ายหรือขวา
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == None:
       #ทำการ update ค่า y ให้ อีกที ว่าอะไรเป็น left เป็น right 
        root = Node(z)
    elif z < y.key:
        y.left = Node(z)
    else:
        y.right = Node(z)
        
#root->left->right        
def preorder(x):
    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""
#left-root-right
def inorder(x):
    return inorder(x.left) + f" {x.key}" + inorder(x.right) if x else ""
        
input()
#รับค่าทีละบรรทัด
node = {}
for s in sys.stdin:
    if s[0] == "p":
        #ถ้าเป็น p ก็ print ถ้าไม่เป็น p ดู ตน. 7 คือ ตัวเลข
        pass
        print(inorder(root))
        print(preorder(root))
    else:
        insert(int(s[7:]))

Submission status: Accepted

Solution code:
import sys
class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x:
        y = x
        if key < x.key:
            x = x.left
        else:
            x = x.right

    if y is None:
        root = Node(key)
    elif key < y.key:
        y.left = Node(key)
    else:
        y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

n = int(input())
for e in sys.stdin:
    if e[0] == 'i':
        insert(int(e[7:]))
    else:
        print(inorder(root))
        print(preorder(root))

Submission status: Accepted

Solution code:
n = int(input())

class Node:
    def __init__(self):
        self.key = -1
        self.parent_id = -1
        self.left_id = -1
        self.right_id = -1


def insert(nodes,z):
    y = -1
    root_id = -1
    for i in range(len(nodes)):
        if nodes[i].parent_id == -1:
            root_id = i
            break

    x = root_id

    while x != -1:
        y = x
        if z.key < nodes[x].key:
            x = nodes[x].left_id
        else:
            x = nodes[x].right_id

    z.parent_id = y
    nodes.append(z)
    z_id = len(nodes) - 1
    if y == -1: pass
    elif z.key < nodes[y].key:
        nodes[y].left_id = z_id
    else:
        nodes[y].right_id = z_id


def pre(node_id):
    pre_list.append(nodes[node_id].key)
    left = nodes[node_id].left_id
    right = nodes[node_id].right_id

    if left != -1:
        pre(left)
    if right != -1:
        pre(right)


def Ino(node_id):
    if nodes[node_id].left_id != -1 :
        Ino(nodes[node_id].left_id)
    ino_list.append(nodes[node_id].key)
    if nodes[node_id].right_id != -1:
        Ino(nodes[node_id].right_id)

nodes = []
for i in range(n):
    cmd = input()
    op = cmd[0]

    if op == "i":
        z = Node()
        number = int(cmd[7:])
        z.key = number

        insert(nodes,z)

    if op =="p":
        pre_list = []
        ino_list = []
        for i in range(len(nodes)):
            if nodes[i].parent_id == -1:
                Ino(i)
                pre(i)
                break


        pre_list = list(map(str, pre_list))
        ino_list = list(map(str, ino_list))
        print(" ", end="")
        print(' '.join(ino_list))
        print(" ", end="")
        print(' '.join(pre_list))

Submission status: Accepted

Solution code:
from sys import stdin
N=int(input())
nodes=[None]*N
class node_tree():
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.brother=None
        self.up=None

def ino(u):

    if u.left is not None:
        ino(u.left)
    print("",u.node,end="")
    if u.right is not None:
        ino(u.right)
def pre(u):
    print("",u.node,end="")
    if u.left is not None:
        pre(u.left)
    if u.right is not None:
        pre(u.right)
def search(u,key):
    if u.node <=key.node:
        if u.right is not None:
            search(u.right,key)
        else:u.right=key
    else:
        if u.left is not None:
            search(u.left,key)
        else:u.left=key
for i in range(N):
    command= list((stdin.readline().strip().split()))
    if len(command)!=1:
        key=int(command[1])
        if i==0:
            nodes[i]=node_tree(key)
        else:
            ins=node_tree(key)
            search(nodes[0],ins)
            nodes[i]=ins
    else:
        ino(nodes[0])
        print()
        pre(nodes[0])
        print()

Submission status: Accepted

Solution code:
n = int(input())
inst_k = [-1]*n
inst = [-1]*n
for i in range(n):
    tmp = input().split()
    inst[i] = tmp[0]
    if len(tmp) == 2:
        inst_k[i] = int(tmp[1])

class BST:
    def __init__(self):
        self.key = []
        self.parent = []
        self.left_child = []
        self.right_child = []
        self.root = -1

    def insert(self,new_key):
        new_node = len(self.key)
        self.key.append(new_key)
        self.left_child.append(-1)
        self.right_child.append(-1)
        self.parent.append(-1)

        searching_node = self.root
        searching_node_parent = -1
        while searching_node != -1:
            searching_node_parent = searching_node
            if new_key < self.key[searching_node]:
                searching_node = self.left_child[searching_node]
            else:
                searching_node = self.right_child[searching_node]
        if searching_node_parent == -1:
            self.root = new_node
        else:
            self.parent[new_node] = searching_node_parent
            if new_key < self.key[searching_node_parent]:
                self.left_child[searching_node_parent] = new_node
            else:
                self.right_child[searching_node_parent] = new_node
    
    def print_clear(self):
        self.preorder_ans = []
        self.inorder_ans = []
    
    def preorder(self,node):
        if node != -1:
            self.preorder_ans.append(self.key[node])
            self.preorder(self.left_child[node])
            self.preorder(self.right_child[node])
    
    def inorder(self,node):
        if node != -1:
            self.inorder(self.left_child[node])
            self.inorder_ans.append(self.key[node])
            self.inorder(self.right_child[node])

tree = BST()
for i in range(n):
    if inst[i] == "insert":
        tree.insert(inst_k[i])
    elif inst[i] == "find":
        pass
    elif inst[i] == "print":
        tree.print_clear()
        tree.preorder(tree.root)
        tree.inorder(tree.root)
        print(" ",end = "")
        print(*tree.inorder_ans)
        print(" ",end = "")
        print(*tree.preorder_ans)

Submission status: Accepted

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

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        x, y = self.root, None
        z = Node()
        z.key = key
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    
    def preOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        print("", r.key, end = '')
        self.preOrder(r.left)
        self.preOrder(r.right)
    
    def inOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        self.inOrder(r.left)
        print("", r.key, end = '')
        self.inOrder(r.right)

tree = BST()
for _ in range(int(input())):
    s = input()
    if s[0] == 'i':
        tree.insert(int(s[7:]))
    else:
        tree.inOrder()
        print("")
        tree.preOrder()
        print("")

Submission status: Accepted

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

T = {}
root = None

def insert_node(key):
    global root
    x = root
    y = None
    z = Node(None, None, None)
    while x != None:
        y = x
        if key < x:
            x = T[x].left
        else:
            x = T[x].right
    z.parent = y
    if y == None:
        root = key
    else:
        if key < y:
            T[y].left = key
        else:
            T[y].right = key
    T[key] = z

def in_print(key, ls):
    if key == None:
        return
    in_print(T[key].left, ls)
    ls.append(key)
    in_print(T[key].right, ls)

def pre_print(key, ls):
    if key == None:
        return
    ls.append(key)
    pre_print(T[key].left, ls)
    pre_print(T[key].right, ls)

def print_node():
    in_ls, pre_ls = [], []
    in_print(root, in_ls)
    pre_print(root, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

N = int(input())
for i in range(N):
    com = input().split()
    if com[0] == 'insert':
        insert_node(int(com[1]))
    elif com[0] == 'print':
        print_node()

Submission status: Accepted

Solution code:
# coding: utf-8

Node = list()
n = int(input())

def insertKey(k):
    idx = len(Node)
    Node.append([k, -1, -1])
    if idx > 0:
        pPrv = -1
        pTmp = 0
        while pTmp != -1:
            pPrv = pTmp
            if k < Node[pTmp][0]:
                pTmp = Node[pTmp][1]
            else:
                pTmp = Node[pTmp][2]
        if Node[-1][0] < Node[pPrv][0]:
            Node[pPrv][1] = idx
        else:
            Node[pPrv][2] = idx

def inOrder(num):
    if num == -1:
        return
    inOrder(Node[num][1])
    print(' {}'.format(Node[num][0]), end = '')
    inOrder(Node[num][2])

def preOrder(num):
    if num == -1:
        return
    print(' {}'.format(Node[num][0]), end = '')
    preOrder(Node[num][1])
    preOrder(Node[num][2])

for i in range(n):
    temp = input().strip()
    if temp[:6] == 'insert':
        insertKey(int(temp[7:]))
    else:
        inOrder(0)
        print('')
        preOrder(0)
        print('')

Submission status: Accepted

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

    def insert(self,t,key):
        '''
        if self.key==None:self.key = key
        elif key<self.key:
            if self.left == None:self.left = Node(key)
            else                :self.left.insert(key)
        else:
            if self.right == None:self.right = Node(key)
            else                 :self.right.insert(key)
        '''
        if t.key == None:
            t.key = key
            return
        y = None 
        x = t
        while x is not None:
            y = x
            if key<x.key:x = x.left
            else        :x = x.right

        if y is None  :t = Node(key)
        elif key<y.key:y.left = Node(key)
        else          :y.right = Node(key)

    def inorder(self):
        if self.left!=None:self.left.inorder()
        print (' %d'%self.key,end = '')
        if self.right!=None:self.right.inorder()

    def preorder(self):
        print (' %d'%self.key,end = '')
        if self.left!=None:self.left.preorder()
        if self.right!=None:self.right.preorder()

    def walk(self):
        self.inorder()
        print ()
        self.preorder()
        print ()

def main():
    Tree = Node()
    q = int(input())
    for _ in range(q):
        com = list(input().split())
        if com[0] == 'insert':
            Tree.insert(Tree,int(com[1]))
        else :
            Tree.walk()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
my_input = sys.stdin.readline


class BinarySearchTree:
    class Node:
        def __init__(self, key):
            __slots__ = ['key', 'left', 'right', 'parent']
            self.key = key
            self.left = None
            self.right = None
            self.parent = None

    def __init__(self):
        self.root = None

    def insert(self, target_key):
        parent = None
        attention = self.root
        target = self.Node(target_key)

        while attention is not None:
            parent = attention
            if target.key < attention.key:
                attention = attention.left
            else:
                attention = attention.right
        target.parent = parent

        if parent is None:
            self.root = target
        elif target.key < parent.key:
            parent.left = target
        else:
            parent.right = target

    def preorder_walk(self, node):
        if node is None:
            return []
        return [node.key] + self.preorder_walk(node.left) + self.preorder_walk(node.right)

    def inorder_walk(self, node):
        if node is None:
            return []
        return self.inorder_walk(node.left) + [node.key] + self.inorder_walk(node.right)


N = int(my_input())
BST = BinarySearchTree()
for _ in range(N):
    command = my_input().split()
    if len(command) == 2:
        BST.insert(int(command[1]))
    else:
        print(' ' + ' '.join(map(str, BST.inorder_walk(BST.root))))
        print(' ' + ' '.join(map(str, BST.preorder_walk(BST.root))))