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: Runtime Error

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

import random
import sys
import os


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

    def __str__(self):
        if self.root == None:
            return None
        else:
            return "TODO"

    def print_inorder(self):
        self.inorder_list = []
        self.__inorder(self.root)
        return self.inorder_list

    def __inorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.__inorder(node.left)
            self.inorder_list.append(node.key)
            self.__inorder(node.right)

    def print_preorder(self):
        self.preorder_list = []
        self.__preorder(self.root)
        return self.preorder_list

    def __preorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.preorder_list.append(node.key)
            self.__preorder(node.left)
            self.__preorder(node.right)

    def insert(self, node):
        """
        :param node: Node
        :return:
        """
        if self.root is None:
            self.root = node
        else:
            x = self.root
            parent_candidate = x

            while x is not None:
                parent_candidate = x
                if x.key > node.key:
                    x = x.left
                else:
                    x = x.right

            # child to parent link
            x = node
            x.parent = parent_candidate

            # parent to child link
            if x.key < x.parent.key:
                x.parent.left = x
            else:
                x.parent.right = x

    def find(self, value):
        """
        :param value:
        :rtype: Node
        :return:
        """
        x = self.root
        while x is not None and x.key != value:
            if x.key > value:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, value):
        found_node = self.find(value)
        if found_node is None:
            print("value is nothing")
        else:
            # has no child
            if found_node.is_leaf():
                # delete link from parent
                print(found_node.parent.left.key)
                print(found_node.key)

                if found_node.parent.left.key == found_node.key:
                    found_node.parent.left = None
                else:
                    found_node.parent.right = None
            else:
                # has one child
                if found_node.has_one_child():
                    one_child = found_node.get_one_child()

                    # change link to parent
                    one_child.parent = found_node.parent

                    # chagne link from parent
                    if found_node.parent.left == found_node:
                        found_node.parent.left = one_child
                    else:
                        found_node.parent.right = one_child

                # has two child
                else:
                    next_section_point = found_node.get_next_section_point()
                    # ?¬???????????????????????????????????????????????¬?????????????????????? p217
                    # ????????????
                    key = next_section_point.key
                    self.delete(next_section_point.key)
                    found_node.key = key


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

    def has_one_child(self):
        if self.left is None and self.right is not None:
            return True
        elif self.left is not None and self.right is None:
            return True
        else:
            return False

    def get_one_child(self):
        if not self.has_one_child():
            return None
        else:
            if self.left is not None:
                return self.left
            else:
                return self.right

    def get_next_section_point(self):
        """?¬??????????????????????"""

        # ????????????????????´???
        if self.right is not None:
            return self.right.get_minimum()
        # ???????????????????????´???????¬???????????????´?????????
        else:
            # ?
            return self.parent

    def is_leaf(self):
        if self.left is None and self.right is None:
            return True
        else:
            return False

    def get_minimum(self):
        if self.left is None:
            return self
        else:
            return self.left.get_minimum()

tree = Tree()
s = input()
n = int(s)
for _ in range(n-1):
    s = input()
    value = int(s.split(" ")[-1])
    node = Node(value)
    tree.insert(node)

in_list = tree.print_inorder()
in_list = map(str, in_list)
print(' ' + ' '.join(in_list))

pre_list = tree.print_preorder()
pre_list = map(str, pre_list)
print(' ' + ' '.join(pre_list))

Submission status: Runtime Error

Solution code:
class Node():
    key = 0
    l = None
    r = None
    def __init__(self, key):
        self.key = key
T = [] * int(5e6)
def insert(z):
    if z == 0: return
    y = None
    x = 0
    while x is not None:
        y = x
        x = (T[x].l if T[z].key < T[x].key else  T[x].r)
    if T[z].key < T[y].key: T[y].l = z
    else: T[y].r = z
def inorder(x):
    if x == None: return;
    inorder(T[x].l);
    print("", T[x].key, end="")
    inorder(T[x].r);
def preorder(x):
    if x == None: return;
    print("", T[x].key, end="")
    preorder(T[x].l);
    preorder(T[x].r);
n = int(input())
for i in range(n):
    s = input()
    if s == "print":
        inorder(0)
        print()
        preorder(0)
        print()
    else:
        x = int(s.split()[1])
        T.append(Node(x))
        insert(i)

Submission status: Runtime Error

Solution code:
# Binary Search Tree1
class BinaryTree():
    def __init__(self):
        self.key = None
        self.parent = None
        self.left = None
        self.right = None

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

def inoder(x):
    if x == No???e: return
    else:
        node = x
        inoder(node.left)
        ino.append(str(node.key))
        inoder(node.right)

def preoder(x):
    if x == None: return
    else:
        node = x
        pre.append(str(node.key))
        preoder(node.left)
        preoder(node.right)

def show(x):
    preoder(x)
    inoder(x)
    print(" ".join(ino))
    print(" ".join(pre))


root = None
n = int(input())
T = []
cnt = 0
for i in range(n):
    L = input().split()
    if L[0] == "insert":
        T.append(BinaryTree())
        T[cnt].key = int(L[1])
        insert(T[cnt])
        cnt += 1
    else:
        pre = []
        ino = []
        show(root)

Submission status: Runtime Error

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

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

def inoder(x):
    if x == No???e: return []
    else:
        r = []
        r.extend(inoder(x.left))
        r.append(str(x.key))
        r.extend(inoder(x.right))
    return r

def preoder(x):
    if x == None: return []
    else:
        r = []
        r.append(str(x.key))
        r.extend(preoder(x.left))
        r.extend(preoder(x.right))
    return r

def show(x):
    print(" ".join(inoder(x)))
    print(" ".join(preoder(x)))


root = None
n = int(input())
for i in range(n):
    L = input().split()
    if L[0] == "insert":
        T = BinaryTree()
        T.key = int(L[1])
        insert(T)
    else:
        show(root)

Submission status: Runtime Error

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

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

def inoder(x):
    if x == No???e: return []
    else:
        r = []
        r.extend(inoder(x.left))
        r.append(str(x.key))
        r.extend(inoder(x.right))
    return r

def preoder(x):
    if x == None: return []
    else:
        r = []
        r.append(str(x.key))
        r.extend(preoder(x.left))
        r.extend(preoder(x.right))
    return r

def show(x):
    print(" ".join(inoder(x)))
    print(" ".join(preoder(x)))


root = None
n = int(input())
for i in range(n):
    L = input().split()
    if L[0] == "insert":
        T = BinaryTree()
        T.key = int(L[1])
        insert(T)
    else:
        show(root)

Submission status: Runtime Error

Solution code:
class Node():
    def __init__(self, id, left=-1, right=-1, parent=-1):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent  
    def show(self):
        print 'node %d: parent = %d, left = %d, right = %d' % (self.id, self.parent, self.left, self.right)

class Stack():
    def __init__(self):
        self.el = []
    def add(self, el):
        self.el.append(el)
    def pop(self):
        return self.el.pop()

def insert(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while x != None:
            y = x
            if z.id < x.id:
                if x.left == -1:
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    break
                x = T[x.right]
        z.parent = x.id
    if y == None:
        rootId = z.id
    elif z.id < y.id:
        y.left = z.id
    else:
        y.right = z.id
    T[z.id] = z
    return T

### input ###
T = {}
a = []
n = int(raw_input())
rootId = None
for i in range(n):
    tmp = raw_input().split()
    if tmp[0] == 'insert':
        T[int(tmp[1])] = Node(int(tmp[1]))
        T = insert(T, Node(int(tmp[1])))
    elif tmp[0] == 'print':
        break

### inorder ###
pos = rootId
st = Stack()
ans = []
while True:
    if T[pos].left != -1 and T[pos].left not in ans:
        if T[pos].right != -1:
            st.add(T[pos].right)
        st.add(pos)
        pos = T[pos].left
    elif T[pos].left == -1 and T[pos].right != -1 and T[pos].right not in ans:
        ans.append(pos)
        pos = T[pos].right
    else:
        ans.append(pos)
        if len(ans) == len(T):
            break
        pos = st.pop()    
print '', ' '.join(map(str, ans))

### preorder ###
pos = rootId
st = Stack()
ans = []
while True:
    ans.append(pos)
    if len(ans) == len(T):
        break
    if T[pos].left != -1 and T[pos].right != -1:
        st.add(T[pos].right)
    if T[pos].left != -1:
        pos = T[pos].left
    elif T[pos].left == -1 and T[pos].right != -1:
        pos = T[pos].rights
    else:
        pos = st.pop()
print '', ' '.join(map(str, ans))

Submission status: Runtime Error

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


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

    def insert(self, key):
        root_node = self.root
        insert_node = Node(key)
        parent_node = None

        while root_node:
            parent_node = root_node
            if insert_node.key < root_node.key:
                root_node = root_node.left
            else:
                root_node = root_node.right

        insert_node.parent = parent_node

        if parent_node is None:
            self.root = insert_node
        elif insert_node.key < parent_node.key:
            parent_node.left = insert_node
        else:
            parent_node.right = insert_node

    def show_preorder(self, node):
        node_list = []

        node_list.append(node.key)
        if node.left is not None:
            node_list.extend(self.show_preorder(node.left))
        if node.right is not None:
            node_list.extend(self.show_preorder(node.right))

        return node_list

    def show_inorder(self, node):
        node_list = []

        if node.left is not None:
            node_list.extend(self.show_inorder(node.left))
        node_list.append(node.key)
        if node.right is not None:
            node_list.extend(self.show_inorder(node.right))

        return node_list

    def print(self):
        print(' ' + *self.show_inorder(self.root))
        print(' ' + *self.show_preorder(self.root))


if __name__ == '__main__':
    tree = BinarySearchTree()

    n = int(input())

    for i in range(n):
        command = input().split()

        if command[0] == 'insert':
            tree.insert(int(command[1]))
        elif command[0] == 'print':
            tree.print()

Submission status: Runtime Error

Solution code:
with open("test.txt", "r") as f:
    class BinarySearchTree:
        def __init__(self):
            self.root = None

        def insert(self, x):
            node = self.Node(x)
            if self.root is None:
                self.root = node
            else:
                here = self.root
                #
                temp = None
                while here is not None:
                    temp = here
                    if x < here.node:
                        here = here.left
                    elif x > here.node:
                        here = here.right
                if x < temp.node:
                    temp.left = node
                elif x > temp.node:
                    temp.right = node

        def inorder(self, answer, address = "root"):
            if address is "root":
                address = self.root
            elif address is None:
                return
            self.inorder(answer, address.left)
            answer.append(address.node)
            self.inorder(answer, address.right)

        def preorder(self, answer, address = "root"):
            if address is "root":
                address = self.root
            elif address is None:
                return
            answer.append(address.node)
            self.preorder(answer, address.left)
            self.preorder(answer, address.right)

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

    query = int(f.readline())
    bt = BinarySearchTree()
    for _ in range(query):
        command = f.readline()
        if command[0] == "i":
            bt.insert(int(command.split(" ")[1]))
        else:
            a = []
            bt.inorder(a)
            print(*a)
            a = []
            bt.preorder(a)
            print(*a)

Submission status: Runtime Error

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

    def insert(self, x):
        node = self.Node(x)
        if self.root is None:
            self.root = node
        else:
            here = self.root
            #
            temp = None
            while here is not None:
                temp = here
                if x < here.node:
                    here = here.left
                elif x > here.node:
                    here = here.right
            if x < temp.node:
                temp.left = node
            elif x > temp.node:
                temp.right = node

    def inorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        self.inorder(answer, address.left)
        answer.append(address.node)
        self.inorder(answer, address.right)

    def preorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        answer.append(address.node)
        self.preorder(answer, address.left)
        self.preorder(answer, address.right)

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

query = int(f.readline())
bt = BinarySearchTree()
for _ in range(query):
    command = f.readline()
    if command[0] == "i":
        bt.insert(int(command.split(" ")[1]))
    else:
        a = []
        bt.inorder(a)
        print(*a)
        a = []
        bt.preorder(a)
        print(*a)

Submission status: Runtime Error

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x = self.root
        y = None
        z = Node(key)
        while x != None:
            y = x
            x = x.left if z.key < x.key else x.right
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            if node:
                inorder(node.left)
                temp += f' {node.key}'
                inorder(node.right)
        def preorder(node):
            if node:
                temp += f' {node.key}'
                preorder(node.left)
                preorder(node.right)
        temp = ''
        inorder(self.root)
        print(temp)
        temp = ''
        preorder(self.root)
        print(temp)

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Runtime Error

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y = self.root, None
        while x != None: x, y = x.left if key < x.key else x.right, x
        if y == None: self.root = Node(key)
        elif key < y.key: y.left = Node(key)
        else: y.right = z
    def print_tree(self):
        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 ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Runtime Error

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(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == -1:
        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 = {}
root = -1
for s in sys.stdin:
    if s[0] == "p":
        print(inorder(root))
        print(preorder(root))
    else:
        insert(node, int(s[7:]))

Submission status: Runtime Error

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(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == -1:
        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 = {}
root = -1
for s in sys.stdin:
    if s[0] == "p":
        print(inorder(root))
        print(preorder(root))
    else:
        insert(int(s[7:]))

Submission status: Runtime Error

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(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == -1:
        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 = {}
root = -1
for s in sys.stdin:
    if s[0] == "p":
        print(inorder(root))
        print(preorder(root))
    else:
        insert(int(s[7:])

Submission status: Runtime Error

Solution code:
from collections import deque
from enum import Enum, auto

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

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = 0
        self.inorder = ''
        self.preorder = ''

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        self.preorder = ''
        def preorder_bfs(s):
            self.preorder += ' ' + str(self.nodes[s].val)
            if  self.nodes[s].left != None:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None:
                preorder_bfs(self.nodes[s].right)
        preorder_bfs(self.root)
        return self.preorder

    def inorder(self):
        self.inorder = ''
        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            if self.nodes[u].left != None:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            self.inorder += ' ' + str(self.nodes[u].val)
            if self.nodes[u].right != None:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()

        inorder_dfs_init(self.root)
        return self.inorder

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print(bst.inorder())
        print(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Runtime Error

Solution code:
from collections import deque
from enum import Enum, auto

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

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = 0
        self.inorder_str = ''
        self.preorder_str = ''

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        self.preorder = ''
        def preorder_bfs(s):
            self.preorder_str += ' ' + str(self.nodes[s].val)
            if  self.nodes[s].left != None:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None:
                preorder_bfs(self.nodes[s].right)
        preorder_bfs(self.root)
        return self.preorder_str

    def inorder(self):
        self.inorder = ''
        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            if self.nodes[u].left != None:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            self.inorder_str += ' ' + str(self.nodes[u].val)
            if self.nodes[u].right != None:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()

        inorder_dfs_init(self.root)
        return self.inorder_str

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print(bst.inorder())
        print(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)