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
input = sys.stdin.readline
n = int(input())

Order = []
for _ in range(n):
    o = input().split()
    Order.append(o)

class Node:
    def __init__(self, key, value, left, right):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        
class BinaryTree:
    def __init__(self):
        self.root = None
        
    def insert(self, key, value):
        if self.root == None:
            node = Node(key, value, None, None)
            self.root = node
        else:
            node = Node(key, value, None, None)
            cmp_node = self.root
            while 1:
                if cmp_node.value > value and cmp_node.left == None:
                    cmp_node.left = node
                    break
                elif cmp_node.value > value and cmp_node.left != None:
                    cmp_node = cmp_node.left
                elif cmp_node.value < value and cmp_node.right == None:
                    cmp_node.right = node
                    break
                elif cmp_node.value < value and cmp_node.right != None:
                    cmp_node = cmp_node.right
        
def mid_search(node):
    if node == None:
        return
    mid_search(node.left)
    print('', node.key, end='')
    mid_search(node.right)
    
def fast_search(node):
    if node == None:
        return
    print('', node.key, end='')
    fast_search(node.left)
    fast_search(node.right)    
        
T = BinaryTree()
for o in Order:
    if o[0] == 'insert':
        T.insert(int(o[1]), int(o[1]))
    if o[0] == 'print':
        mid_search(T.root)
        print()
        fast_search(T.root)
        print()

Solution (Python):

import sys


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


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

    def insert(self, x):
        new = Node(x)
        x_parent = self.root
        next = self.root

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

        if x_parent is None:
            self.root = new
        elif x < x_parent.key:
            new.parent = x_parent
            x_parent.left = new
        else:
            new.parent = x_parent
            x_parent.right = new
        return

    def preorder(self, node):
        print(' {}'.format(node.key), end='')

        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
        return

    def inorder(self, node):
        if node.left:
            self.inorder(node.left)

        print(' {}'.format(node.key), end='')

        if node.right:
            self.inorder(node.right)


m = int(input())
tree = Tree()

for i in range(m):
    command = list(sys.stdin.readline().strip().split())
    if command[0] == 'print':
        tree.inorder(tree.root)
        print()
        tree.preorder(tree.root)
        print()
    else:
        num = command[1]
        command = command[0]
        num = int(num)
        tree.insert(num)

Solution (Python):
class Node:

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

    def append(self, node):
        if self.value > node.value:
            if self.left is None:
                node.parent = self
                self.left = node
            else:
                self.left.append(node)
        else:
            if self.right is None:
                node.parent = self
                self.right = node
            else:
                self.right.append(node)

    def in_parse(self, node, lst):
        if node is None:
            return
        self.in_parse(node.left, lst)
        lst.append(str(node.value))
        self.in_parse(node.right, lst)

    def pre_parse(self, node, lst):
        if node is None:
            return
        lst.append(str(node.value))
        self.pre_parse(node.left, lst)
        self.pre_parse(node.right, lst)


class BinaryTree:

    def __init__(self):
        self.root = None

    def insert(self, value):
        node = Node(value)
        if self.root is None:
            self.root = node
        else:
            self.root.append(node)

    def in_parse(self):
        lst = []
        self.root.in_parse(self.root, lst)
        return lst

    def pre_parse(self):
        lst = []
        self.root.pre_parse(self.root, lst)
        return lst


def main():
    n = int(input())
    tree = BinaryTree()

    for _ in range(n):
        line = input().split(' ')
        command = line[0]
        if command == 'insert':
            v = int(line[1])
            tree.insert(v)
        else:
            print(' ' + ' '.join(tree.in_parse()))
            print(' ' + ' '.join(tree.pre_parse()))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class Node:
    __slots__ = ['value', 'parent', 'left', 'right']
    def __init__(self, value: int, parent: 'Node' = None):
        self.value = value
        self.parent = parent
        self.left: Node = None
        self.right: Node = None
    def inParse(self):
        if self.value == None:
            return
        if self.left != None:
            self.left.inParse()
        print(' {}'.format(self.value), end='')
        if self.right != None:
            self.right.inParse()
    def preParse(self):
        if self.value == None:
            return
        print(' {}'.format(self.value), end='')
        if self.left != None:
            self.left.preParse()
        if self.right != None:
            self.right.preParse()

class BinarySearchTree:
    __slots__ = ['root']
    def __init__(self):
        self.root: Node = None
    def insert(self, x: int):
        if self.root == None:
            self.root = Node(x)
            return
        parent, current = None, self.root
        while current:
            parent = current
            if x < current.value:
                current = current.left
            else:
                current = current.right
        if x < parent.value:
            parent.left = Node(x, parent)
        else:
            parent.right = Node(x, parent)

def main():
    tree = BinarySearchTree()
    n = int(input())
    for _ in range(n):
        inp = input()
        if inp[0] == 'i':
            com, num = inp.split()
            tree.insert(int(num))
        else:
            tree.root.inParse()
            print()
            tree.root.preParse()
            print()

if __name__=='__main__': main()

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

l, r = {}, {}

def insertnode(num, x):
    """xには毎回rootを設定（rootから順に比較してし、適した場所に追加）"""
    if num < x:
        if x in l:
            if l[x] != 3000000000:
                insertnode(num, l[x])
            else:
                l[x] = num
                return
        else:
            l[x] = num
            return
    else:
        if x in r:
            if r[x] != 3000000000:
                insertnode(num, r[x])
            else:
                r[x] = num
                return
        else:
            r[x] = num
            return

def inorder(num):
    if num == 3000000000:
        return
    if num in l:
        inorder(l[num])
    else:
        l[num] = 3000000000
        inorder(l[num])
    print(' ' + str(num), end='')
    if num in r:
        inorder(r[num])
    else:
        r[num] = 3000000000
        inorder(r[num])

def preorder(num):
    if num == 3000000000:
        return
    print(' ' + str(num), end='')
    if num in l:
        preorder(l[num])
    else:
        l[num] = 3000000000
        preorder(l[num])
    if num in r:
        preorder(r[num])
    else:
        r[num] = 3000000000
        preorder(r[num])

for i in range(m):
    order = input()
    if i == 0:
        global root
        root = int(order[7:])
        continue
    if order[0] == 'i':
        num = int(order[7:])
        insertnode(num, root)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):
class binaryTreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

n = int(input())
root = None
for index in range(n):
    inputL = input().split()
    if inputL[0] == 'insert':
        if index == 0:
            root = binaryTreeNode(int(inputL[1]))
        else:
            def walkNode(node, val, parent):
                if node != None:
                    if node.val > val:
                        walkNode(node.left, val, node)
                    else:
                        walkNode(node.right, val, node)
                else:
                    if parent.val > val:
                        parent.left = binaryTreeNode(val)
                    else:
                        parent.right = binaryTreeNode(val)
            walkNode(root, int(inputL[1]), None)
    else:
        inL = [] 
        def lookNodeIn(node):
            if node != None:
                lookNodeIn(node.left)
                inL.append(node.val)
                lookNodeIn(node.right)
        lookNodeIn(root)
        preL = []
        def lookNodePre(node):
            if node != None:
                preL.append(node.val)
                lookNodePre(node.left)
                lookNodePre(node.right)
        lookNodePre(root)
        print(' '+' '.join(list(map(str, inL))))
        print(' '+' '.join(list(map(str, preL))))

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

def bst_insert(node, label):
    if node is None:
        return Node(label)
   
    elif label< node.label:
        node.left = bst_insert(node.left, label)
    else:
        node.right = bst_insert(node.right, label)
    return node


def bst_inorder(node):
    global In
    if (node.left is not None):
        bst_inorder(node.left)
    In.append(node.label)
    if (node.right is not None):
        bst_inorder(node.right)
    return

def bst_preorder(node):
    global Pre
    Pre.append(node.label)
    if (node.left is not None):
        bst_preorder(node.left)
    if (node.right is not None):
        bst_preorder(node.right)
    return 

n= int(input())
tree = None
for i in range(n):
    cmmd = list(input().split( ))
    if cmmd[0] == "insert":
        k =int(cmmd[1])
        tree = bst_insert(tree, k)
    else:
        In =[]
        bst_inorder(tree)
        print("",*In)
        Pre =[]
        bst_preorder(tree)
        print("",*Pre)

Solution (Python):
class Node():
    def __init__(self, key, p, l, r):
        self.key, self.p, self.l, self.r = key, p, l, r


class BinarySearchTree():
    def __init__(self):
        self.tree = []
        self.root = -1

    def insert(self, key):
        y = -1  
        x = self.root
        while x != -1:
            y = x
            if key < self.tree[x].key:
                x = self.tree[x].l
            else:
                x = self.tree[x].r
        self.tree.append(Node(key, y, -1, -1))
        z = len(self.tree) - 1
        if y == -1:
            self.root = z
        elif key < self.tree[y].key:
            self.tree[y].l = z
        else:
            self.tree[y].r = z

    def preorder_traversal(self, u):
        if u == -1:
            return
        print(' ' + str(self.tree[u].key), end='')
        self.preorder_traversal(self.tree[u].l)
        self.preorder_traversal(self.tree[u].r)

    def inorder_traversal(self, u):
        if u == -1:
            return
        self.inorder_traversal(self.tree[u].l)
        print(' ' + str(self.tree[u].key), end='')
        self.inorder_traversal(self.tree[u].r)


def main():
    n = int(input())
    bst = BinarySearchTree()
    for _ in range(n):
        order = input().split()
        if order[0] == 'insert':
            key = int(order[1])
            bst.insert(key)
        elif order[0] == 'print':
            bst.inorder_traversal(0)
            print('')
            bst.preorder_traversal(0)
            print('')


if __name__ == '__main__':
    main()

Solution (Python):

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


def insert(T, z):
    y = None
    x = T
    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:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

    return T


def preorder(T, ret):
    ret.append(T.key)

    if T.left is not None:
        preorder(T.left, ret)

    if T.right is not None:
        preorder(T.right, ret)


def inorder(T, ret):
    if T.left is not None:
        inorder(T.left, ret)

    ret.append(T.key)

    if T.right is not None:
        inorder(T.right, ret)


def main():
    m = int(input())
    Tree = None
    for i in range(m):
        cmd, *v = input().split()
        if cmd == "print":
            print(" ", end="")
            inans = []
            inorder(Tree, inans)
            print(*inans)
            print(" ", end="")
            preans = []
            preorder(Tree, preans)
            print(*preans)
        else:
            z = int(v[0])
            znode = Node(z)
            Tree = insert(Tree, znode)


if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self,key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.key)
def inorder(r): 
    if (r.left != None):
        inorder(r.left)
    print(' ' + str(r.key), end ='')
    if (r.right != None):
        inorder(r.right)
def preorder(r):  
    print(" "+str(r.key), end ='')  
    if (r.left != None):  
        preorder(r.left) 
    if (r.right != None):
        preorder(r.right) 
root = None
def insert(z,root):
    y = None
    x = root
    while x != 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
n = int(input())
command = str(input())
if command[0]=="i":
    root = Node(int(command[7:]))
else:
    print()
for i in range(n-1):
    com = str(input())
    if com[0] == "i":
        insert(Node(int(com[7:])),root)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):
from typing import Optional


class Node:
    def __init__(self, arg_parent: Optional["Node"], arg_key: int,
                 arg_left: Optional["Node"], arg_right: Optional["Node"]):
        self.parent = arg_parent
        self.key = arg_key
        self.left = arg_left
        self.right = arg_right


def print_preorder(node: Node) -> None:
    print(f" {node.key}", end="")
    if node.left is not None:
        print_preorder(node.left)
    if node.right is not None:
        print_preorder(node.right)


def print_inorder(node: Node) -> None:
    if node.left is not None:
        print_inorder(node.left)
    print(f" {node.key}", end="")
    if node.right is not None:
        print_inorder(node.right)


def insert(root: Optional[Node], node: Node) -> Node:
    y: Optional[Node] = None
    x = 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:
        root = node
    elif node.key < y.key:
        y.left = node
    else:
        y.right = node

    assert root is not None
    return root


if __name__ == "__main__":
    root: Optional[Node] = None
    node_num = int(input())
    for _ in range(node_num):
        command, *value = input().split()
        if "insert" == command:
            root = insert(root, Node(None, int(value[0]), None, None))
        elif "print" == command:
            assert root is not None
            print_inorder(root)
            print()
            print_preorder(root)
            print()
        else:
            pass

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

parent_node = None

        
def getParent():
    tmp_node = Nodes
    while Nodes.parent != None:
        tmp_node = tmp_node.parent
    return tmp_node    

def printPreorder(u):
    if u == None:
        return
    print(" ", u.key, sep="", end="")
    printPreorder(u.left)
    printPreorder(u.right)
    
def printInorder(u):
    if u == None:
        return
    printInorder(u.left)
    print(" ", u.key, sep="", end="")
    printInorder(u.right)

n = int(input())


Nodes = []
for i in range(n):
    tmp_node = Node(0)
    Nodes.append(tmp_node)

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        key = int(cmd[1])

        insert_node = Nodes[i]
        insert_node.key = key
        key_parent = None
        x = parent_node
            
        while x != None:
            key_parent = x
            if insert_node.key < x.key:
                x = x.left
            else:
                x = x.right
        insert_node.parent = key_parent
            
        if key_parent == None:
            parent_node = insert_node
        elif insert_node.key < key_parent.key:
            key_parent.left = insert_node
        else:
            key_parent.right = insert_node
        
        
        
        
    else:
        printInorder(parent_node)
        print("")
        printPreorder(parent_node)
        print("")

Solution (Python):
root = None

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

def preorder(T):
    if T is None:
        return
    print(' ' + str(T.key), end='')
    preorder(T.left)
    preorder(T.right)

def inorder(T):
    if T is None:
        return
    inorder(T.left)
    print(' ' + str(T.key), end='')
    inorder(T.right)

def find(T, z):
    if T is None:
        return False
    if T.key == z:
        return True

    if z < T.key and T.left is not None:
        return find(T.left, z)
    elif z > T.key and T.right is not None:
        return find(T.right, z)
    else:
        return False

def insert(T, z):
    global root
    if T is None:
        root = Node(z, None, None)
        return

    
    

    parent = T
    while True:
        if parent.left is None and parent.right is None:
            break
        elif parent.left is None and z < parent.key:
            break
        elif parent.right is None and z > parent.key:
            break

        
        

        if z < parent.key:
            parent = parent.left

        else:
            parent = parent.right


    if z < parent.key:
        node = Node(z, None, None)
        parent.left = node
    elif z > parent.key:
        node = Node(z, None, None)
        parent.right = node

n = int(input())

for i in range(n):
    s = input().split()
    if s[0] == 'insert':
        insert(root, int(s[1]))
    elif s[0] == 'find':
        if find(root, int(s[1])):
            print('yes')
        else:
            print('no')
    else:
        inorder(root)
        print('')
        preorder(root)
        print('')

Solution (Python):
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

    def insert(self, v):
        x = TreeNode(v)
        if not self.root:
            self.root = x
            return

        r = self.root
        while r is not None:
            parent = r
            if x.val < r.val:
                r = r.left
            else:
                r = r.right

        if x.val < parent.val:
            parent.left = x
        else:
            parent.right = x

    def in_order(self):
        def helper(node):
            if not node:
                return
            helper(node.left)
            res.append(node.val)
            helper(node.right)

        res = []
        helper(self.root)
        return res

    def pre_order(self):
        def helper(node):
            if not node:
                return
            res.append(node.val)
            helper(node.left)
            helper(node.right)

        res = []
        helper(self.root)
        return res


test = BST()
n = int(input())
for _ in range(n):
    order = input()
    if order.startswith("insert"):
        i, x = order.split()
        test.insert(int(x))
    else:
        print(" ",end="")
        print(*test.in_order())
        print(" ",end="")
        print(*test.pre_order())

Solution (Python):
NIL = -1


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


class BinaryTree():
    def __init__(self, node):
        self.root = node

    def insert(self, key):
        if self.root.key == NIL:
            self.root.key = key
            return

        now = self.root
        while now != NIL:
            parent = now
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                raise
        
        insert = Node(key, parent)

        if   insert.key < parent.key:
            parent.left = insert
        elif insert.key > parent.key:
            parent.right = insert
        else:
            raise

    def treewalk_inorder(self, node):
        if isinstance(node, int):
            return

        self.treewalk_inorder(node.left)
        print(f" {node.key}", end="")
        self.treewalk_inorder(node.right)

    def treewalk_preorder(self, node):
        if isinstance(node, int):
            return

        print(f" {node.key}", end="")
        self.treewalk_preorder(node.left)
        self.treewalk_preorder(node.right)



n = int(input())

root_node = Node()
binary_tree = BinaryTree(root_node)


for _ in range(n):

    command, *list_num = input().split()

    if   command == "insert":
        k = int(list_num[0])
        binary_tree.insert(k)
    elif command == "print":
        binary_tree.treewalk_inorder(root_node)
        print()
        binary_tree.treewalk_preorder(root_node)
        print()
    else:
        raise

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

    def isRoot(self):
        return self.parent is None

    def preorder(self, arr):
        arr.append(str(self.id))
        if self.left is not None:
            self.left.preorder(arr)
        if self.right is not None:
            self.right.preorder(arr)

    def inorder(self, arr):
        if self.left is not None:
            self.left.inorder(arr)
        arr.append(str(self.id))
        if self.right is not None:
            self.right.inorder(arr)

    def postorder(self, arr):
        if self.left is not None:
            self.left.postorder(arr)
        if self.right is not None:
            self.right.postorder(arr)
        arr.append(str(self.id))

def insert(root, z):
    y = None
    x = root
    while x is not None:
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right

    z.parent = y

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


m = int(input())
root = None

for i in range(m):
    arr = input().split()
    if arr[0] == 'print':
        arr = []
        root.inorder(arr)
        print('', ' '.join(arr))
        arr = []
        root.preorder(arr)
        print('', ' '.join(arr))
        continue

    id = int(arr[1])
    if root is None:
        root = Node(id)
        continue

    insert(root, Node(id))

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

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

    def insert(self, data):
        p = None 
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while n is not None:
                p = n
                if data < n.data:
                    n = n.left
                else:
                    n = n.right

            if (data < p.data):
              p.left = Node(data)
            else:
              p.right = Node(data)

    def inorder(self):
        self._inorder(self.root)
    def _inorder(self,node):
        if node is not None:
            self._inorder(node.left)
            print(" " + str(node.data), end="")
            self._inorder(node.right)
    def preorder(self):
        self._preorder(self.root)
    def _preorder(self,node):
        if node is not None:
            print(" " + str(node.data), end="")
            self._preorder(node.left)
            self._preorder(node.right)

n = int(input())
t = BST()
for i in range(0, n):
  line = input().split()

  if line[0] == "insert":
    t.insert(int(line[1]))
  elif line[0] == "print":
    t.inorder()
    print()
    t.preorder()
    print()

Solution (Python):
class BST:
  def __init__(self):
    self.root = None
  
  def insert(self, data):
    z = Node(data)
    y = None
    x = self.root

    while x:
      y = x
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    z.parent = y
    if y == None:
      self.root = z
    elif z.data < y.data:
      y.left = z
    else:
      y.right = z

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


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

  def inorder(self):
    in_list = []
    if self.left:
      in_list += self.left.inorder()
    in_list += [self.data]
    if self.right:
      in_list += self.right.inorder()
    return in_list
  
  def preorder(self):
    pre_list = []
    pre_list += [self.data]
    if self.left:
      pre_list += self.left.preorder()
    
    if self.right:
      pre_list += self.right.preorder()
    return pre_list

tree = BST()
n = int(input())
for _ in range(n):
  inp = input().split()
  if len(inp) == 2:
    tree.insert(int(inp[1]))
  else:
    tree.print()

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

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

    return T, root

def printPreorderList(p):
    if p == None:
        return
    print("",p.key,end = "")
    printPreorderList(p.left)
    printPreorderList(p.right)

def printInorderList(p):
    if p == None:
        return
    printInorderList(p.left)
    print("",p.key,end = "")
    printInorderList(p.right)
'''
def findRoot(T):
    if T == []:
        return None
    root = T[0].p
    while root != None:
        root = root.p
    return root
'''
n = int(input())
T=[]
root = None
for ni in range(n):
    s = input()
    if s[0] == "i":
        s, key = s.split()
        key = int(key)
        T, root = insert(T, Node(key), root)
    elif s[0] == "p":
        printInorderList(root)
        print()
        printPreorderList(root)
        print()