Problem:
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 ≠ 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.

Solution (Python):
import sys


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

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


class Tree:

    def __init__(self):
        self.root = None


def insert(T, z):
    '''
    T : Tree
    z : 要素
    '''

    p = None  
    x = T.root

    while x:  
        p = x  
        if z.key < x.key:
            x = x.left  
        else:
            x = x.right  

    if p is None:  
        T.root = z
    elif z.key < p.key:
        p.left = z  
    else:
        p.right = z  


def inorder(v):

    if v.left is not None:
        inorder(v.left)

    print("", v.key, end="")

    if v.right is not None:
        inorder(v.right)

    return


def preorder(r):

    print("", r.key, end="")

    if r.left is not None:
        preorder(r.left)
    if r.right is not None:
        preorder(r.right)

    return


def display(v):

    inorder(v)
    print("")
    preorder(v)
    print("")
    return


def main():

    T = Tree()

    

    N = int(sys.stdin.readline().rstrip())
    for _ in range(N):
        op = sys.stdin.readline().rstrip().split()

        if len(op) == 2:
            v = Node(int(op[1]))
            insert(T, v)

        if len(op) == 1:
            display(T.root)


main()

Solution (Python):
class BinaryTree:
    def __init__(self, left, right, parent):
        self.left = left
        self.right = right
        self.parent = parent
        self.key = None
        self.root = False
        

def insert(T, z):
    global root
    
    y = -1
    try:
        x = root
    except:
        x = -1
        root = z
        T[z].root = True
    
    while x != -1:
        y = x
        if T[z].key < T[x].key:
            x = T[x].left
        else:
            x = T[x].right
    T[z].parent = y
    
    if y == -1:
        pass
    
    elif T[z].key < T[y].key:
        T[y].left = z
        
    else:
        T[y].right = z
    
def preParse(u):
    if u == -1:
        return 0
    print(" " + str(T[u].key), end="")
    preParse(T[u].left)
    preParse(T[u].right)

def inParse(u):
    if u == -1:
        return 0
    inParse(T[u].left)
    print(" " + str(T[u].key), end="")
    inParse(T[u].right)

m = int(input().rstrip())

z = 0
T = []
for _ in range(m):
    T.append(BinaryTree(-1, -1, -1))

for _ in range(m):
    command = input().rstrip()
    if command =="print":
        inParse(root)
        print()
        preParse(root)
        print()
    else:
        T[z].key = int(command.split(" ")[-1])
        insert(T, z)
        z += 1

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

def insert(T:dict,z:int):
    global root
    y = -1
    x = root
    while x != -1:
        y = x
        if z < x:
            x = T[x].left
        else:
            x = T[x].right
    T[z] = Node(y,-1,-1)
    
    if y == -1:
        root= z
    elif z < y:
        T[y].left = z
    else:
        T[y].right = z

def inorder(u:int):
    if u == -1:
        return 
    inorder(T[u].left)
    print(" "+str(u),end="")
    inorder(T[u].right)

def preorder(u:int):
    if u == -1:
        return 
    print(" "+str(u),end="")
    preorder(T[u].left)
    preorder(T[u].right)

n = int(input())
root = -1
T = {}
for _ in range(n):
    scan = input().split()
    if len(scan) == 1:
        inorder(root)
        print()
        preorder(root)
        print()
    else:
        insert(T,int(scan[-1]))

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

class Tree:
    root = None
    preorder_list = []
    inorder_list = []
    def __init__(self):
        pass
    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 == None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def display(self):
        
        self.inorder(self.root)
        self.preorder(self.root)
        print(' '+' '.join(map(str, self.inorder_list)))
        print(' '+' '.join(map(str, self.preorder_list)))
        pass

    def preorder(self, node):
        if node == None:
            return
        self.preorder_list.append(node.key)
        if node.left is not None:
            self.preorder(node.left)
        if node.right is not None:
            self.preorder(node.right)

    def inorder(self, node):
        if node == None:
            return
        if node.left is not None:
            self.inorder(node.left)
        self.inorder_list.append(node.key)
        if node.right is not None:
            self.inorder(node.right)

n = int(input())
command_list = [list(input().split()) for _ in range(n)]

tree = Tree()
for command in command_list:
    if command[0] == 'insert':
        node = Node(int(command[1]))
        tree.insert(node)
        
    if command[0] == 'print':
        tree.display()
        tree.preorder_list = []
        tree.inorder_list = []

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = self.right = None
    def preorder(self):
        L = [self.key]
        if self.left: L += self.left.preorder()
        if self.right: L += self.right.preorder()
        return L
    def inorder(self):
        L = []
        if self.left: L += self.left.inorder()
        L.append(self.key)
        if self.right: L += self.right.inorder()
        return L

def insert(t, z):
    y = None
    x = t
    while x:
        y = x 
        x = x.left if z.key < x.key else x.right
    z.parent = y
    if not y: 
        return z
    if z.key < y.key:
        y.left = z 
    else:
        y.right = z 
    return t

t = None
m = int(input())
for _ in range(m):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        t = insert(t, Node(int(cmd[1])))
    if cmd[0] == 'print':
        print('', *t.inorder())
        print('', *t.preorder())

Solution (Python):
import sys






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


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

def inorder(inorder_list, node):
    if node.left is not None:
        inorder(inorder_list, node.left)
    inorder_list.append(str(node.key))
    if node.right is not None:
        inorder(inorder_list, node.right)
    return inorder_list
        
def preorder(preorder_list, node):
    preorder_list.append(str(node.key))
    if node.left is not None:
        preorder(preorder_list, node.left)
    if node.right is not None:
        preorder(preorder_list, node.right)
    return preorder_list
        
root = None

input()
for o in sys.stdin:
    if o[0]=='i':
        insert(int(o[7:]))
    else:
        x = root
        inorder_list = inorder([], x)
        print(' '+' '.join(inorder_list))
        preorder_list = preorder([], x)
        print(' '+' '.join(preorder_list))

Solution (Python):
import sys
sys.setrecursionlimit(2**20)  


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


def pre_parse(T, u, pre_ls):
    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, ROOT, z):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()  
        x = ROOT
        while x is not None:  
            next_parent = x  
            if z < x:  
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        
        if z < next_parent:
            T[next_parent].left = z
        else:
            T[next_parent].right = z


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())
T = {}
for i in range(n):
    tmp = input()
    if i == 0:
        ROOT = int(tmp[7:])
    if tmp[0] == "p":
        print_result(T)
    else:
        insert(T, ROOT, int(tmp[7:]))

Solution (Python):
n=int(input())

tree={}
root=None

def insert(tree,number):
    y=None
    x=root
    while x!=None:
        y=x
        if number<x:
            x=tree[y][0]
        else:
            x=tree[y][1]

    if number<y:
        tree[y][0]=number
    else:
        tree[y][1]=number

def preorder(tree,i):
    if i==None:
        return
    print(" {}".format(str(i)),end="")
    preorder(tree,tree[i][0])
    preorder(tree,tree[i][1])

def inorder(tree,i):
    if i==None:
        return
    inorder(tree,tree[i][0])
    print(" {}".format(str(i)),end="")
    inorder(tree,tree[i][1])

for i in range(n):
    tmp=list(input().split())
    if tmp[0]=="insert":
        number=int(tmp[1])
        if root==None:
            root=number
            tree[root]=[None,None]
        else:
            tree[number]=[None,None]
            insert(tree,number)
    
    else:
        inorder(tree,root)
        print()
        preorder(tree,root)
        print()

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

class Node():
    key = None
    p = None
    left = None
    right = None

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

class BinarySearchTree():
    root = None

    def insert(self, 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.p = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def print_nodes(self):
        inorder = []
        preorder = []

        def dfs(v):
            v_key = v.key
            preorder.append(v_key)
            if v.left is not None:
                dfs(v.left)
            inorder.append(v_key)
            if v.right is not None:
                dfs(v.right)

        dfs(self.root)

        print('', *inorder)
        print('', *preorder)

def resolve():
    n = I()
    T = BinarySearchTree()
    for _ in range(n):
        q = LSS()
        if q[0]=='insert':
            z = Node(int(q[1]))
            T.insert(z)
        else:
            T.print_nodes()

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(2 ** 20)  


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 = []

Solution (Python):
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()

Solution (Python):
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()])))

Solution (Python):
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 
    y = None 
    
    while x is not None:
        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) + " "+ 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))

Solution (Python):

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:
            
            bst.in_order_print()
            print()
            bst.pre_order_print()
            print()


if __name__ == '__main__':
    resolve()

Solution (Python):
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

    
    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
            
        else:
            xidx=x.right
            
    z.parent=yidx

    if yidx==-1:
        root=zidx
        
    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()
    
    

def main():
    global commands

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

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

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
import sys

class Node():
    
    __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

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

def preorder(x):
    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""

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":
        
        pass
        print(inorder(root))
        print(preorder(root))
    else:
        insert(int(s[7:]))

Solution (Python):
import sys

class Node():
    __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
def insert(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == None:
        root = Node(z)
    elif z < y.key:
        y.left = Node(z)
    else:
        y.right = Node(z)
        
def preorder(x):
    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""

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":
        pass
        print(inorder(root))
        print(preorder(root))
    else:
        insert(int(s[7:]))

Solution (Python):
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))