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:
# coding: utf-8

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

class NodeTree:
    def __init__(self, root=None):
        self.root = root
        
    def insert(self,z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.me < x.me:
                x = x.left
            else:
                x = x.right
        z.parent = y
        
        if y == None:
            self.root = z
        elif z.me < y.me:
            y.left = z
        else:
            y.right = z
    
    def getPreorder(self, node, ans):
        ans.append(node)
        if node.left != None:
            self.getPreorder(node.left, ans)
        if node.right != None:
            self.getPreorder(node.right, ans)
            
    def getInorder(self, node, ans):
        if node.left != None:
            self.getInorder(node.left, ans)
        ans.append(node)
        if node.right != None:
            self.getInorder(node.right, ans)

        
def printAns(ans):
    for a in ans:
        print(" " + str(a.me),end="")
    print()
    
m = int(input().rstrip())
nt = NodeTree()
for i in range(m):
    line = input().rstrip().split()
    if line[0] == "insert":
        nt.insert(Node(int(line[1]),None,None))
    else:
        ans = []
        nt.getInorder(nt.root,ans)
        printAns(ans)
        ans = []
        nt.getPreorder(nt.root,ans)
        printAns(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

    def insert(self, v):
        cur = self.root
        cur_p = None
        while cur != None:
            cur_p = cur
            if v < cur.value:
                cur = cur.left
            elif v > cur.value:
                cur = cur.right

        n = Node(v, cur_p)
        if cur_p == None:
            self.root = n
        elif v < cur_p.value:
            cur_p.left = n
        else:
            cur_p.right = n

    def preorder(self):

        def rec_preorder(t=self.root):
            if t != None:
                print(" ", t.value, sep="", end="")
                rec_preorder(t.left)
                rec_preorder(t.right)

        rec_preorder()
        print()

    def inorder(self):

        def rec_inorder(t=self.root):
            if t != None:
                rec_inorder(t.left)
                print(" ", t.value, sep="", end="")
                rec_inorder(t.right)

        rec_inorder()
        print()

m = int(stdin.readline().rstrip())
t = BST()
for _ in range(m):
    q = stdin.readline().rstrip().split()
    if q[0] == "insert":
        t.insert(int(q[1]))
    elif q[0] == "print":
        t.inorder()
        t.preorder()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import defaultdict

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

root = None
nodes = defaultdict(lambda: None)

def insert(z):
    global root
    # yはxの親
    y = None
    x = root
    # zの親となるべきノードを探す
    while x is not None:
        y = x
        if z.key < x.key:
            # 左の子に移動
            x = nodes[x.left]
        else:
            # 右の子に移動
            x = nodes[x.right]
    if y is None:
        z.par = -1
    else:
        z.par = y.key
    
    if y is None:
        # Tが空の場合
        root = z
    elif z.key < y.key:
        # zをyの左の子にする
        y.left = z.key
    else:
        # zをyの右の子にする
        y.right = z.key

def tree_walk(node):
    preo.append(node.key)
    if node.left != -1:
        tree_walk(nodes[node.left])
    ino.append(node.key)
    if node.right != -1:
        tree_walk(nodes[node.right])
    return

N = INT()

for _ in range(N):
    instr = input()
    if instr == 'print':
        preo = []
        ino = []
        tree_walk(root)
        print('', *ino)
        print('', *preo)
    else:
        _, key = instr.split()
        key = int(key)
        node = Node(key)
        nodes[key] = node
        insert(node)

Submission status: Accepted

Solution code:
class STNode:
    def __init__(self, k, l, r):
        self.key = k
        self.left = l
        self.right = r

def STinsert(h, z):
    p = None
    while True:
        if h.key == -1:
            break
        p = h
        if z.key < h.key:
            h = h.left
        else:
            h = h.right
    if z.key < p.key:
        p.left = z
    else:
        p.right = z

def preorder(head, h, A):
    if h.key == -1:
        return
    A.append(h.key)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.key == -1:
        return
    inorder(head, h.left, B)
    B.append(h.key)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

n = int(input())
NULLnode = STNode(-1, None, None)

first = list(input().split())
head = STNode(int(first[1]), NULLnode, NULLnode)
for i in range(n-1):
    temp = list(input().split())
    if temp[0] == "insert":
        z = STNode(int(temp[1]), NULLnode, NULLnode)
        STinsert(head, z)
    else:
        A = []
        B = []
        inorder(head, head, B)
        preorder(head, head, A)

Submission status: Accepted

Solution code:

class Node:

    def __init__(self, key: int) -> None:
        self.key = key
        self.parent = None
        self.left = None
        self.right = None


def input_line() -> (str, int):
    line = input().split()
    if line[0] == 'insert':
        return 'insert', int(line[1])
    else:
        return line[0], None


def preorder(tree: Node) -> None:
    """先行順巡回。"""
    print(f' {tree.key}', end='')
    if tree.left is not None:
        preorder(tree.left)
    if tree.right is not None:
        preorder(tree.right)


def inorder(tree: Node) -> None:
    """中間順巡回。"""
    if tree.left is not None:
        inorder(tree.left)
    print(f' {tree.key}', end='')
    if tree.right is not None:
        inorder(tree.right)


def insert(new_node: Node) -> None:
    """二分探索木に挿入する。"""
    global root  # rootはglobalに共有する。
    parent = None
    x = root

    # new_nodeを付け加える節(parent)を探索。
    while x is not None:
        parent = x
        if new_node.key < x.key:
            x = x.left
        else:
            x = x.right
    new_node.parent = parent

    # new_nodeの子供を設定。
    if parent is None:  # treeが空だった場合は、rootにnew_nodeを設定。
        # print(f'key: {new_node.key} op: new node')
        root = new_node
    elif new_node.key < parent.key:
        # print(f'key: {new_node.key} op: left')
        parent.left = new_node
    else:
        # print(f'key: {new_node.key} op: right')
        parent.right = new_node


root = None  # treeの根を表す。初期値はNone。
N = int(input())
for _i in range(N):
    order, val = input_line()
    if order == 'insert':
        node = Node(val)
        insert(node)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

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

    def __repr__(self):
        return str(self.key)

def insert(T, z):
    y = None
    x = T 
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    #print(x,y,z)
    if y == None:
        #print("Y==None")
        T = z
        print(T)
    elif z.key<y.key:
        #print("z.key<y.key")
        y.left = z
    else:
        #print("z.key<y.key")
        y.right = z

def printPreorder(x):
    if x == None:
        return
    printPreorder(x.left)
    print(end=' ')
    print(x,end='')
    printPreorder(x.right)

def printMidorder(x):
    if x == None:
        return
    print(end=' ')
    print(x,end='')
    printMidorder(x.left)
    printMidorder(x.right)

def printal(x):
    printPreorder(x)
    print()
    printMidorder(x)
    print()


N = int(input())
Q = input().split()
T = Node(int(Q[1]),None,None,None)
for i in range(N-1):
    Q = input().split()
    if Q[0] == "print":
        printal(T)
        continue
    insert(T,Node(int(Q[1]),None,None,None))

Submission status: Accepted

Solution code:
def insert(z):
    global root
    y = NIL
    x = root
    #print(x)
    while x != NIL:
        y = x
        if z < x:
            x = TL[x]
        else:
            x = TR[x]
    TP[z] = y

    if y == NIL:
        root = z
    elif z < y:
        TL[y] = z
    else:
        TR[y] = z


def inorder(u):
    if u == NIL:
        return
    inorder(TL[u])
    print(' ', end='')
    print(u, end='')
    inorder(TR[u])


def preorder(v):
    if v == NIL:
        return
    print(' ', end='')
    print(v, end='')
    preorder(TL[v])
    preorder(TR[v])


TR = {}
TL = {}
TP = {}
NIL = None
root = NIL
m = int(input())
data = [input().split() for _ in range(m)]
#print(data)
for i in data:
    if i[0][0] == 'i':
        TR[int(i[1])] = TL[int(i[1])] = NIL
        insert(int(i[1]))
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

Solution code:
import sys


class Node:
    __slots__ = ['key', 'parent', 'left', 'right']

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


def insert(root, z):
    if root is None:
        return z

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

    z.parent = y

    if z.key < y.key:
        y.left = z
    else:
        y.right = z

    return root


def inorder(node):
    if not node:
        return
    yield from inorder(node.left)
    yield node.key
    yield from inorder(node.right)


def preorder(node):
    if not node:
        return
    yield node.key
    yield from preorder(node.left)
    yield from preorder(node.right)


def print_tree(root):
    print(''.join(' ' + str(key) for key in inorder(root)))
    print(''.join(' ' + str(key) for key in preorder(root)))


root = None

n = int(sys.stdin.readline())
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command == 'insert':
        root = insert(root, Node(int(args[0])))
    else:
        print_tree(root)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C&lang=jp
# Binary Search Tree I
# 2018.12.01 yonezawa

import sys
input = sys.stdin.readline
import cProfile

class node:
    def __init__(self,nodeid):
        self.parent = None
        self.c_left = None
        self.c_right = None
        self.nodeid = nodeid
    def setChild(self,n,cn=None):
        if (cn == None):
            cn = self
        if ( cn.nodeid < n):
            if (cn.c_right == None):
                cn.c_right = node(n) 
                cn.c_right.parent =  cn 
                return cn.c_right
            else:
                return self.setChild(n,cn.c_right)
        else:
            if (cn.c_left == None):
                cn.c_left = node(n) 
                cn.c_left.parent =  cn
                return cn.c_left 
            else:
                return self.setChild(n,cn.c_left)

    def getPreorder(self,r1=[]):
        r1.append(self.nodeid)
        if (self.c_left != None):
            r1 = self.c_left.getPreorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPreorder(r1)
        return r1       
    def getInorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getInorder(r1)
        r1.append(self.nodeid)
        if (self.c_right != None):
            r1 = self.c_right.getInorder(r1)
        return r1       
    def getPostorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getPostorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPostorder(r1)
        r1.append(self.nodeid)
        return r1       
    def find(self,n):
        if self.nodeid == n:
            return True
        if self.nodeid > n:
            if (self.c_left == None ):
                return False
            return self.c_left.find(n)
        else:
            if  (self.c_right == None):
                return False
            return self.c_right.find(n)

    def findObject(self,n):
        if self.nodeid == n:
            return self
        if self.nodeid > n:
            if (self.c_left == None ):
                return None
            return self.c_left.findObject(n)
        else:
            if  (self.c_right == None):
                return None
            return self.c_right.findObject(n)

    def deleteNum(self,n):
        i = self.findObject(int(n))
        if i == None:
            return False
        self.deleteObject(i)
        return True

    def deleteObject(self,obj):
        p = obj.parent
        x = obj
        if x.c_left == None and x.c_right == None:
            if p.c_right.nodeid == x.nodeid:
                p.c_right = None
            else:
                p.c_left = None
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left == None and x.c_right != None:
            if p.c_right != None and p.c_right.nodeid == obj.nodeid:
                p.c_right = x.c_right
                x.c_right.parent = p
            else:
                p.c_left = x.c_right
                x.c_right.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left != None and x.c_right == None:
            if p.c_right.nodeid == x.nodeid:
                p.c_right = x.c_left
                x.c_left.parent = p
            else:
                p.c_left = x.c_left
                x.c_left.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        y = self.findMinObject(x.c_right)
        x.nodeid = y.nodeid
        p = y.parent
        x = y
        if x.c_left == None and x.c_right == None:
            if p.c_right != None and p.c_right.nodeid == x.nodeid:
                p.c_right = None
            else:
                p.c_left = None
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left == None and x.c_right != None:
            if p.c_right.nodeid == obj.nodeid:
                p.c_right = x.c_right
                x.c_right.parent = p
            else:
                p.c_left = x.c_right
                x.c_right.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

    def findMinObject(self,obj):
        i = obj
        while i != None and i.c_left != None:
            i = i.c_left
        return i

    
    def getRoot(self):
        if (self.parent == None):
            return self
        return self.parent.getRoot()

def printNodeList(nodelist,caption):
    for i in nodelist:
        a = b = c = None
        if (i != None ):
            a = i.nodeid
        if (i.c_left != None):
            b = i.c_left.nodeid
        if (i.c_right != None):
            c = i.c_right.nodeid 
        if ( a != None and (b != None or c != None)):
            print (caption,a,b,c)
            
def main():
    n = int(input())
    nodelist = []
    root = None
    for i in range(n):
        l = list(map(str,input().split()))
        if (l[0] == "print" and root != None):
            print("",*root.getInorder([]))
            print("",*root.getPreorder([]))
        elif (l[0] == "insert"):
            d = int(l[1])
            if ( root == None):
                root = node(d)
                nodelist.append(root)
            else:
                #root.setChild(d)
                nodelist.append(root.setChild(d))
        elif (l[0] == "find"):
            d = int(l[1])
            r = root.find(d)
            if (r == True):
                print ("yes")
            else:
                print ("no")
        elif (l[0] == "delete"):
            #printNodeList(nodelist,"Debug:rm "+str(l[1])+":")
            root.deleteNum(l[1])
            #printNodeList(nodelist,"Debug:post rm "+str(l[1])+":")

        
if __name__ == '__main__':
    main()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

Submission status: Accepted

Solution code:
import sys
class Node:
    parent = -1
    left = -1
    right = -1

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

    def __repr__(self):
        return "key:{},parent:{},left:{},right:{}".format(self.key, self.parent, self.left, self.right)

root_node_no = -1

def insert(nodes :dict, in_node :Node):
    global root_node_no

    cur_node_no = root_node_no
    parent_node_no = -1
    while cur_node_no != -1:
        parent_node_no = cur_node_no
        if in_node.key < cur_node_no:
            cur_node_no = nodes[cur_node_no].left
        else:
            cur_node_no = nodes[cur_node_no].right

    in_node.parent = parent_node_no

    if root_node_no == -1:
        root_node_no = in_node.key
    elif in_node.key < parent_node_no:
        nodes[parent_node_no].left = in_node.key
    else:
        nodes[parent_node_no].right = in_node.key

    nodes[in_node.key] = in_node

def inorder_tree_walk(nodes, node_no ,inorder):
    if node_no == -1:
        return
    inorder_tree_walk(nodes, nodes[node_no].left, inorder)
    inorder.append(node_no)
    inorder_tree_walk(nodes, nodes[node_no].right, inorder)

def preorder_tree_walk(nodes, node_no, preorder):
    if node_no == -1:
        return
    preorder.append(node_no)
    preorder_tree_walk(nodes, nodes[node_no].left, preorder)
    preorder_tree_walk(nodes, nodes[node_no].right, preorder)
    pass

def main():
    num_com = int(input())
    commands = sys.stdin.readlines()
    nodes = {}
    for i in range(num_com):
        if commands[i][0] == 'i':
            insert(nodes, Node(int(commands[i][7:])))
        elif commands[i][0] == 'p':
            # inorder
            inorder = []
            inorder_tree_walk(nodes, root_node_no, inorder)
            print(" " + " ".join(map(str, inorder)))
            # preorder
            preorder = []
            preorder_tree_walk(nodes, root_node_no, preorder)
            print(" " + " ".join(map(str, preorder)))


main()

Submission status: Accepted

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


def insert(root,node):#rootを根に持つ２分探索木にnodeを追加する
    if(root.key <= node.key):
        if(root.right is None):
            root.right=node
        else:
            insert(root.right,node)
    
    else:
        if(root.left is None):
            root.left=node
        else:
            insert(root.left,node)


def Preorder(root,order):
    order.append(root.key)
    if(root.left is not None):
        Preorder(root.left,order)
    
    if(root.right is not None):
        Preorder(root.right,order)




def Inorder(root,order):
    if(root.left is not None):
        Inorder(root.left,order)
    
    order.append(root.key)

    if(root.right is not None):
        Inorder(root.right,order)




n=int(input())

root=None

for loop in range(n):
    ope=input().split()

    if(ope[0]=="insert"):
        tmp_node=Node(int(ope[1]))
        try:
            insert(root,tmp_node)
        except:
            root=tmp_node
    
    else:
        in_order=[]
        p_order=[]
        
        Inorder(root,in_order)
        Preorder(root,p_order)

        for x in in_order:
            print(f" {x}",end="")
        print()
        for x in p_order:
            print(f" {x}",end="")
        print()

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 sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            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 print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
     
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

Submission status: Accepted

Solution code:
from sys import stdin

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

class BinarySearchTree(object):
    def __init__(self):
        self.tree = {}
        self.root = None

    def insert(self, z):
        if not self.tree:
            self.tree[z] = Node(parent=-1)
            self.root = z
        else:
            x = self.root
            while x != None:
                y = x
                if z < x:
                    x = self.tree[x].left
                else:
                    x = self.tree[x].right

            self.tree[z] = Node(parent=y)
            if z < y:
                self.tree[y].left = z
            else:
                self.tree[y].right = z

    def print_nodes(self):
        A = [] # Preorder
        B = [] # Inorder
        def walk_tree(u):
            if u == None:
                return
            r = self.tree[u].right
            l = self.tree[u].left
            A.append(u)
            walk_tree(l)
            B.append(u)
            walk_tree(r)

        walk_tree(self.root)
        print(" ", end="")
        print(*B, sep=" ")
        print(" ", end="")
        print(*A, sep=" ")

def read_and_print_BSTree(bst, n):
    for _ in range(n):
        cmd = stdin.readline().strip().split()
        if cmd[0] == 'insert':
            bst.insert(int(cmd[1]))
        elif cmd[0] == 'print':
            bst.print_nodes()

n = int(input())
bst = BinarySearchTree()
read_and_print_BSTree(bst, n)

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
    y = None  # xの親
    x = root
    while x:
        y = x
        x = x.left if key < x.key else x.right
    if y is None:  # Tが空の場合
        root = Node(key)
    elif key < y.key:
        y.left = Node(key)
    else:
        y.right = Node(key)

def in_order(node):
    if node is None:
        return ''
    return in_order(node.left) + f' {node.key}' + in_order(node.right)
def pre_order(node):
    if node is None:
        return ''
    return f' {node.key}' + pre_order(node.left) + pre_order(node.right)
input()
for e in sys.stdin:
    if e[0] == 'i':
        insert(int(e[7:]))
    else:
        print(in_order(root))
        print(pre_order(root))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

from sys import stdin


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

    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 print_inorder(self):
        def rec(node):
            if not node:
                return
            else:
                rec(node.left)
                print("", node.key, end="")
                rec(node.right)

        rec(self.root)
        print()

    def print_preorder(self):

        def rec(node):
            if not node:
                return
            else:
                print("", node.key, end="")
                rec(node.left)
                rec(node.right)

        rec(self.root)
        print()


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

    def __repr__(self):
        return "Node({}, {}, {})".format(
            self.val, self.left, self.right)


def main():
    _ = int(stdin.readline())
    T = Tree()

    for line in stdin:
        cmd, *args = line.split()
        if cmd == "insert":
            T.insert(Node(int(args[0])))
        elif cmd == "print":
            T.print_inorder()
            T.print_preorder()


main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
        
    def insert(self, z):
        if z.key < self.key:
            if self.left:
                self.left.insert(z)
            else:
                self.left = z
                z.parent = self
        else:
            if self.right:
                self.right.insert(z)
            else:
                self.right = z
                z.parent = self

    def preo(self):
        tmp = ""
        tmp += " " + str(self.key)
        if self.left:
            tmp += self.left.preo()
        if self.right:
            tmp += self.right.preo()
        return tmp
    
    def ino(self):
        tmp = ""
        if self.left:
            tmp += self.left.ino()
        tmp += " " + str(self.key)
        if self.right:
            tmp += self.right.ino()
        return tmp
    
    
m = int(input())
T = {}
for i in range(m):
    com = input().split()
    if com[0] == "insert":
        node = Node(int(com[1]))
        if len(T)==0:
            T[node.key] = node
            T["root"] = node
        else:
            T["root"].insert(node)
    else:
        print(T["root"].ino())
        print(T["root"].preo())