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
input = sys.stdin.readline
print = sys.stdout.write

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

class BinarySearchTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        parent = self.root
        if parent is None:
            self.root = Node(data)
            return
        while parent:
            parent_old = parent
            parent = parent.left if data < parent.data else parent.right
        if data < parent_old.data:
            parent_old.left = Node(data)
        else:
            parent_old.right = Node(data)


def print_preorder(node):
    print(" {}".format(node.data))
    if node.left:
        print_preorder(node.left)
    if node.right:
        print_preorder(node.right)

def print_inorder(node):
    if node.left:
        print_inorder(node.left)
    print(" {}".format(node.data))
    if node.right:
        print_inorder(node.right)

if __name__ == "__main__":
    n = int(input())
    binary_search_tree = BinarySearchTree()
    for _ in range(n):
        operation, *num = input().split()
        if num:
            binary_search_tree.insert(int(num[0]))
        elif binary_search_tree.root is not None:
            print_inorder(binary_search_tree.root)
            print("\n")
            print_preorder(binary_search_tree.root)
            print("\n")

Submission status: Accepted

Solution code:
# Bibary Search Tree

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

root = None

class Node:
    def __init__(self,
                 parent=None,
                 left=None,
                 right=None):
        self.parent = parent
        self.left = left  # 左の子ノード
        self.right = right  # 右の子ノード

# 先行順巡回
def pre_parse(T: dict, u: int, pre_ls: list):
    # 深さ優先探索特有の即時終了条件
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  # より左の方から深さ優先探索
    pre_parse(T, T[u].right, pre_ls)

# 中間順巡回
def in_parse(T, u, in_ls):
    if u == None:
        return
    # 左→中→右の順に巡回
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)

# 挿入
def insert(T, z):
    global root
    T[z] = Node()
    y = None # xの親
    x = root # Tの根
    while (x is not None):
        y = x # xの親を設定
        if z < x:
            x = T[x].left # 左の子へ移動
        else:
            x = T[x].right # 右の子へ移動
    T[z].parent = y # zの親にyを設定
    if (y is None):
        root = z
    elif (z < y):
        T[y].left = z # yの左の子にする
    else:
        T[y].right = z # yの右の子にする


def find(T,  ROOT, k):
    x = ROOT # 訪問中のノード
    while T[x] is not None and x != k:
        if (k < x):
            T[x].left = x
        else:
            T[x].right = x
    return x

def print_result(T):
    pre_ls, in_ls = [], []
    in_parse(T, root, in_ls)
    pre_parse(T, root, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

N = int(input())
lst = [input().split() for i in range(N)]
T = {}
for i, c in enumerate(lst):
    if c[0] == 'insert':
        z = int(c[1])
        insert(T, z)
    elif c[0] == 'print':
        print_result(T)
    elif c[0] == 'find':
        is_find = find(T, root, z)
        if is_find is None:
            print('no')
        else:
            print('Yes')

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.order_list = []
    def insert(self, z):
        y = None
        x = self.root
        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 walk_preorder(self, node):
        if node == None:
            return None
        self.order_list.append(node.key)
        self.walk_preorder(node.left)
        self.walk_preorder(node.right)
    def walk_inorder(self, node):
        if node == None:
            return None
        self.walk_inorder(node.left)
        self.order_list.append(node.key)
        self.walk_inorder(node.right)
    def print_nodes(self):
        self.order_list = []
        self.walk_inorder(self.root)
        inorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(inorder_str))
        self.order_list = []
        self.walk_preorder(self.root)
        preorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(preorder_str))
        
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

n = int(input())
tree = BinarySearchTree()
for _ in range(n):
    command = input().split(' ')
    if len(command) == 1:
        tree.print_nodes()
    else:
        opecode, operand = command[0], int(command[1])
        node = Node(operand)
        tree.insert(node)

Submission status: Accepted

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

root = None
def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z[2] < x[2]:
            x = x[0]
        else:
            x = x[1]
    z[3] = y

    if y is None:
        root = z
    elif z[2] < y[2]:
        y[0] = z
    else:
        y[1] = z

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0] is not None:
            dfs(nd[0])
        s1.append(v)
        if nd[1] is not None:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    else:
        insert([None, None, int(V[0]), None])
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
"""
二分探索木を構成する
"""
import copy

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

class Tree:
    def insert_root_node(self, new_id):
        global root_node #途中でインスタンス化すると水の泡なんですよ
        root_node = Node(new_id)

    def insert_node(self, root_id, new_id): #new_idは追加するノード
        compare_node = root_node #はじめはrootから比較スタート
        new_node = Node(new_id) #インスタンス化
        while compare_node != None: #compare_nodeが存在するとき
            #この下の一行は最重要アイディア
            #親の可能性がある時，とりあえず代入して情報を記録しておく
            new_node.parent = compare_node 
            #右か左か
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        #compare_node == Noneの時，上の２つの分岐のどっちからきたかわからない
        #そのため，親と比較し直す必要がある
        if new_node.parent.node_id < new_id:
            new_node.parent.right = Node(new_id)
        else:
            new_node.parent.left = Node(new_id)

def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)


tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if root_node == None: #何も入ってない時
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(root_id, new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    
class Tree():
    def __init__(self, root=None):
        self.root = root
    
    def insert(self, node):
        y = None
        x = self.root
        while x is not None:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
        
        node.parent = y
        if y is None:   # Tree が空だった場合
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node
    
    def print_inorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            work(node.left)
            print('', node.key, end='')
            work(node.right)

        work(self.root)
        print()
    
    def print_preorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            print('', node.key, end='')
            work(node.left)
            work(node.right)

        work(self.root)
        print()


import sys

n = int(input())
T = Tree()
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command[0] == 'i':   # insert key
        T.insert(Node(int(args[0])))
    else:   # print
        T.print_inorder_tree_walk()
        T.print_preorder_tree_walk()

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 ''


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:
class Node():
    def __init__(self, parent=-1, left=-1, right=-1):
        self.parent = parent
        self.left = left
        self.right = right


class Tree(dict):
    def __init__(self, obj={}):
        if isinstance(obj, dict):
            super().__init__(obj)
        else:
            raise TypeError
        self.root = -1

    def insert_key(self, key):
        node = Node()
        parent = -1  # targetの親
        target = self.root  # 探索中のkey
        while target != -1:
            parent = target
            if key < target:
                target = self[target].left
            else:
                target = self[target].right
        node.parent = parent
        self[key] = node
        if parent == -1:  # Tが空の場合、最上位の場合
            self.root = key
        elif key < parent:
            self[parent].left = key
        else:
            self[parent].right = key

    def find(self, key):
        target = self.root
        while True:
            if target == key:
                return True
            if key < target:
                target = self[target].left
            else:
                target = self[target].right
            if target == -1:
                return False

    def __preorder(self, id):
        if id == -1:
            return []
        return [id] + self.__preorder(self[id].left) + self.__preorder(self[id].right)

    def __inorder(self, id):
        if id == -1:
            return []
        return self.__inorder(self[id].left) + [id] + self.__inorder(self[id].right)

    def __postorder(self, id):
        if id == -1:
            return []
        return self.__postorder(self[id].left) + self.__postorder(self[id].right) + [id]

    def __preorder_print(self, id):
        if id == -1:
            pass
        else:
            print(" {}".format(id), end="")
            self.__preorder_print(self[id].left)
            self.__preorder_print(self[id].right)

    def __inorder_print(self, id):
        if id == -1:
            pass
        else:
            self.__inorder_print(self[id].left)
            print(" {}".format(id), end="")
            self.__inorder_print(self[id].right)

    def __postorder_print(self, id):
        if id == -1:
            pass
        else:
            self.__postorder_print(self[id].left)
            self.__postorder_print(self[id].right)
            print(" {}".format(id), end="")

    def order_list(self, order_type):
        if order_type == 0:
            return self.__preorder(self.root)
        elif order_type == 1:
            return self.__inorder(self.root)
        else:
            return self.__postorder(self.root)

    def print(self):
        # self.__inorder_print(self.root)
        # print("\n", end="")
        # self.__preorder_print(self.root)
        # print("\n", end="")
        print(" {}".format(" ".join(map(str, self.order_list(1)))))
        print(" {}".format(" ".join(map(str, self.order_list(0)))))


def main():
    n = int(input())
    tree = Tree()
    for _ in range(n):
        operation = input()
        if operation[0] == "i":
            tree.insert_key(int(operation.split()[1]))
        elif operation[0] == "f":
            if tree.find(int(operation.split()[1])):
                print("yes")
            else:
                print("no")
        else:
            tree.print()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def insert(tree,node):
    parent=None
    child=root
    while child is not None:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    if node<parent:tree[parent][0]=node
    else:tree[parent][1]=node


def In_order(node):
    if node is None:return
    In_order(tree[node][0])
    print(" {}".format(node), end="")
    In_order(tree[node][1])


def Pre_order(node):
    if node is None:return
    print(" {}".format(node), end="")
    Pre_order(tree[node][0])
    Pre_order(tree[node][1])


n=int(input())
tree,root={},None
for i in range(n):
    order=input().split()
    if order[0]=="print":
        In_order(root);print()
        Pre_order(root);print()
    elif order[0]=="insert":
        num=int(order[1])
        if root is None:
            root=num
            tree[root]=[None,None]
        else:
            tree[num]=[None,None]
            insert(tree,num)

Submission status: Accepted

Solution code:
#! /usr/bin/env python


class NodeBintree:

    def __init__(self, key, parent=None):
        self.key = key
        # self.parent = parent
        self.left = None
        self.right = None

    def insert_node (self, n):
        if (self.key is None) or (self.key > n.key):
            if self.left is None:
                self.left = n
                # n.parent = self
            else:
                self.left.insert_node(n)
        else:
            if self.right is None:
                self.right = n
                # n.parent = self
            else:
                self.right.insert_node(n)

    def traverse_inorder (self):
        ret = ""

        if self.left is not None:
            ret += self.left.traverse_inorder()
            # for less in self.left.traverse_inorder():
            #     yield less

        if self.key is not None:
            ret += " {0}".format(self.key)
            # print(" {0}".format(self.key), end="")
            # yield
            # yield self.key
            # yield " {0}".format(self.key)

        if self.right is not None:
            ret += self.right.traverse_inorder()
            # for more in self.right.traverse_inorder():
            #     yield more
        return ret

    def traverse_preorder (self):
        ret = ""

        if self.key is not None:
            ret += " {0}".format(self.key)
            # print(" {0}".format(self.key), end="")
            # yield
            # yield self.key
            # yield " {0}".format(self.key)

        if self.left is not None:
            ret += self.left.traverse_preorder()
            # for less in self.left.traverse_preorder():
            #     yield less

        if self.right is not None:
            ret += self.right.traverse_preorder()
            # for more in self.right.traverse_preorder():
            #     yield more
        return ret

def proc_inputs ():
    num_inputs = int(input())
    inputs = [proc_command(input().split()) for i in range(num_inputs)]
    return inputs

def proc_command (l):
    if len(l) > 1:
        arg = l[1]
    else:
        arg = None
    return {"command": l[0], "arg": arg}

def execute_command (tree, command):
    if command["command"] == "insert":
        tree.insert_node(NodeBintree(int(command["arg"])))
        # return tree

    elif command["command"] == "print":
        print(tree.traverse_inorder() )
        # print()
        print(tree.traverse_preorder() )
        # print()
        #     pass
        # print("")
        # for n in tree.traverse_preorder():
        #     pass
        # print("")
        # print("".join([" {0}".format(n) for n in tree.traverse_inorder()]))
        # print("".join([" {0}".format(n) for n in tree.traverse_preorder()]))

    return


def main ():
    inputs = proc_inputs()
    # print(inputs)
    tree = NodeBintree(None)
    # map(execute_command, tree, inputs)
    for command in inputs:
        execute_command(tree, command)
    exit(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


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

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

def printInOrder(z):
    if z == None:
        return
    if z.left != None:
        printInOrder(z.left)
    inorder.append(str(z.key))
    #print(z.key, end = " ")
    if z.right != None:
        printInOrder(z.right)
        
def printPreOrder(z):
    if z == None:
        return
    #print(z.key, end = " ")
    preorder.append(str(z.key))
    if z.left != None:
        printPreOrder(z.left)
    if z.right != None:
        printPreOrder(z.right)

root = None


n = int(input())
for i in range(n):
    command = input()
    if command[0] == "i":
        com,num = command.split()
        z = Node(int(num))
        insert(root, z)
        if root == None:
            root = z
    else:
        inorder = []
        printInOrder(root)
        print(" ", end = "")
        print(' '.join(inorder))
        preorder = []
        printPreOrder(root)
        print(" ", end = "")
        print(' '.join(preorder))

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.lcs = {}
        self.rcs = {}
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = key
            self.lcs[key] = None
            self.rcs[key] = None
            return
        parent = self.root
        while True:
            if key < parent:
                if self.lcs[parent] is None:
                    self.lcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.lcs[parent]
            else:
                if self.rcs[parent] is None:
                    self.rcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.rcs[parent]

    def _print(self, cur):
        self.preorder.append(cur)
        if self.lcs[cur]:
            self._print(self.lcs[cur])
        self.inorder.append(cur)
        if self.rcs[cur]:
            self._print(self.rcs[cur])

    def print(self):
        self.preorder = []
        self.inorder = []
        self._print(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))


T = BinarySearchTree()
N = int(input())
for _ in range(N):
    s = input().split()
    if s[0] == 'insert':
        T.insert(int(s[1]))
    else:
        T.print()

Submission status: Accepted

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

class Tree:
    def __init__(self):
        self.root = None
        self.list = []
    
    def insert(self, node_tobe_added):
            y = None #「xの親」って書いてあるけど、「zの親」では？
            x = self.root
            while x != None:
                #ここで親を設定する。xを一つずつ葉に進めて、yに代入する。yがｚの親になる。
                y = x
                if node_tobe_added.key < x.key:
                    x = x.left
                else:
                    x = x.right
            #ここでyがzの親に設定される。
            node_tobe_added.parent = y 
            
            #yがNoneなら何もないということなのでzがrootになる。
            if y == None:
                self.root = node_tobe_added
            elif node_tobe_added.key < y.key:
                #node_tobe_addedをyの左の子にする
                y.left = node_tobe_added
            else:
                #node_tobe_addedをyの右の子にする
                y.right = node_tobe_added
                
    def preParse(self, node):
        if node == None:
            return
        self.list.append(node.key)
        self.preParse(node.left)
        self.preParse(node.right)
    
    def inParse(self, node):
        if node == None:
            return
        self.inParse(node.left)
        self.list.append(node.key)
        self.inParse(node.right)

T = Tree()

N = int(input())
for i in range(N):
        order, *key = input().split() #printの場合はkeyがないので、*をつけて配列として扱う。
        if order == "print":
            T.list = []
            T.inParse(T.root)
            print(" " + " ".join(map(str, T.list)))
            T.list = []
            T.preParse(T.root)
            print(" " + " ".join(map(str, T.list)))
        else:#insertの場合
            T.insert(Node(int(key[0])))

Submission status: Accepted

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

class BinaryTree():
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            parentnode = curnode = self.root
            while curnode != None:
                parentnode = curnode
                if curnode.value > value:
                    curnode = curnode.left
                else:
                    curnode = curnode.right
            if value > parentnode.value:
                parentnode.right = Node(value)
            else:
                parentnode.left = Node(value)

    def preorder(self, root):
        if root == None:
            pass
        else:
            print(' %d' % root.value, end='')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root == None:
            pass
        else:
            self.inorder(root.left)
            print(' %d' % root.value, end='')
            self.inorder(root.right)

if __name__ == '__main__':
    n = int(input())
    binarytree = BinaryTree()
    for _ in range(n):
        common = input()
        if common[0] == 'i':
            binarytree.insert(int(common[7:]))
        else:
            binarytree.inorder(binarytree.root)
            print()
            binarytree.preorder(binarytree.root)
            print()

Submission status: Accepted

Solution code:

class Node:
    key = None
    parent = None
    left = None
    right = None

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


def insert(key):
    global T
    global root

    new_node = Node(key)
    T.append(new_node)

    if root is None:
        root = new_node

    else:
        y = None  # 親
        x = root  # 子

        while x is not None:
            y = x
            if key < x.key:
                x = x.left
            else:
                x = x.right

        new_node.parent = y
        if new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node


def in_order(node, order):
    if node is None:
        return

    in_order(node.left, order)
    order.append(node.key)
    in_order(node.right, order)


def pre_order(node, order):
    if node is None:
        return

    order.append(node.key)
    pre_order(node.left, order)
    pre_order(node.right, order)


m = int(input())
T = []
root = None

for i in range(m):
    order = input()

    if order.startswith('print'):
        output = []
        in_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

        output = []
        pre_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

    else:
        order, value = order.split()
        value = int(value)
        insert(value)

Submission status: Accepted

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

def insert(z):
    global root
    if root==None:
        root=Node(z)
    else:
        x=root
        while True:
            if z<x.key:
                if x.left:
                    x=x.left
                else:
                    x.left=Node(z)
                    break
            else:
                if x.right:
                    x=x.right
                else:
                    x.right=Node(z)
                    break
def inorder(z):
    if z==None:
        return []
    else:
        return inorder(z.left)+[z.key]+inorder(z.right)
def preorder(z):
    if z==None:
        return []
    else:
        return [z.key]+preorder(z.left)+preorder(z.right)
root=None
n=int(input())
for _ in range(n):
    p=input()
    if p[0]=="i":
        insert(int(p[7:]))
    else:
        print("",*inorder(root))
        print("",*preorder(root))