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):



def insert(root, insert_node):
    focus_node = root
    parent = None
    while not focus_node == None:
        parent = focus_node
        if focus_node["data"]  > insert_node["data"]:
            focus_node = focus_node["left"]
        else:
            focus_node = focus_node["right"]

    if parent["data"] > insert_node["data"]:
        parent["left"] = insert_node
        insert_node["parent"] = parent
    else:
        parent["right"] = insert_node
        insert_node["parent"] = parent

def get_preorder(node):
    if node == None:
        return []
    r = []
    r.append(str(node["data"]))
    r.extend(get_preorder(node["left"]))
    r.extend(get_preorder(node["right"]))

    return r
    
def get_inorder(node):
    if node == None:
        return []
    r = []
    r.extend(get_inorder(node["left"]))
    r.append(str(node["data"]))
    r.extend(get_inorder(node["right"]))

    return r

def delete_tree(root, target):
    delete_node = None
    focus_node = root
    parent = None
    node_direction = ""
    while focus_node:
        if target == focus_node["data"]:
            delete_node = focus_node
            break
        elif focus_node["data"] < target:
            parent = focus_node
            node_direction = "right"
            focus_node = focus_node["right"]
        else:
            parent = focus_node
            node_direction = "left"
            focus_node = focus_node["left"]

    if delete_node == None:
        return

    while True:
        if delete_node["left"] == None and delete_node["right"] == None:
            parent[node_direction] = None
            break
        elif delete_node["left"] and delete_node["right"]:
            p = get_inorder(root)
            next_num = int(p[p.index(str(delete_node["data"])) + 1])
            delete_node["data"] = next_num
            delete_node = find_tree(root, next_num)
            parent = delete_node["parent"]
            if parent == None:
                node_direction = None
            elif parent["left"] == delete_node:
                node_direction = "left"
            else:
                node_direction = "right"
        else:
            if delete_node["left"]:
                parent[node_direction] = delete_node["left"]
                delete_node["left"]["parent"] = parent
            else:
                parent[node_direction] = delete_node["right"]
                delete_node["right"]["parent"] = parent
            break

    
def find_tree(root, target):
    focus_node = root

    while not focus_node == None:
        if focus_node["data"] == target:
            return focus_node
        elif focus_node["data"] < target:
            focus_node = focus_node["right"]
        else:
            focus_node = focus_node["left"]
    
    return None
    
def print_tree(root):
    print(" " + " ".join(get_inorder(root)))
    print(" " + " ".join(get_preorder(root)))
    
def main():
    
    n_line = int(input())
    input_list = [input() for i in range(n_line)]
    root = {"left":None, "right": None, "data":int(input_list[0].split()[1]), "parent": None}

    for line in input_list[1:]:
        if line == "print":
            print_tree(root)
        else:
            split_line = line.split()
            if split_line[0] == "insert":
                node = {"left":None, "right": None, "data":int(split_line[1]), "parent":None}
                insert(root, node)
            elif split_line[0] == "find":
                if find_tree(root, int(split_line[1])):
                    print("true")
                else:
                    print("none")
            elif split_line[0] == "delete":
                delete_tree(root, int(split_line[1]))
        
        

if __name__ == "__main__":
    main()

Solution (Python):
class Node(object):
    root = None

    """ ????????¨????????? """
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.height = None

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

    @classmethod
    def walk_preorder(cls, node):
        """ ??????????????? """
        
        
        print(' {0}'.format(node.key), end='')
        if node.left != None:
            
            cls.walk_preorder(node.left)
        if node.right != None:
            
            cls.walk_preorder(node.right)
        

    @classmethod
    def walk_inorder(cls, node):
        """ ??????????????? """
        
        if node.left != None:
            
            cls.walk_inorder(node.left)
        
        print(' {0}'.format(node.key), end='')
        if node.right != None:
            
            cls.walk_inorder(node.right)
        

    def get_type(self):
        if self.parent:
            return 'root'
        elif self.left == None and self.right == None:
            return 'leaf'
        else:
            return 'internal node'

    def get_depth(self):
        if self.parent == None:
            return 0
        else:
            depth = 1
            t = self.parent
            while t.parent != None:
                t = t.parent
                depth += 1
            return depth

    def get_height(self):
        if self.height:
            return self.height
        h_left = 0
        h_right = 0
        if self.left != None:
            h_left = self.left.get_height() + 1
        if self.right != None:
            h_right = self.right.get_height() + 1
        self.height = max(h_left, h_right)
        return self.height

    def get_degree(self):
        degree = 0
        if self.left != None:
            degree += 1
        if self.right != None:
            degree += 1
        return degree

    def get_sibling(self):
        if self.parent == None:
            return -1
        p = self.parent
        if p.left != self and p.left != None:
            return p.left
        if p.right != self and p.right != None:
            return p.right


def process_node_data(node_data):
    last = None
    for inst in node_data:
        if inst[0] == 'print':
            result = Node.walk_inorder(last.root)
            print('')
            
            result = Node.walk_preorder(last.root)
            
            print('')
        else:
            node_key = int(inst[1])
            new_node = Node(node_key)
            last = Node.insert(new_node)


def flatten(l):
    """ http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python """
    import collections
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el


if __name__ == '__main__':
    
    num_of_nodes = int(input())
    node_data = [input().split(' ') for _ in range(num_of_nodes)]
    
    
    
    
    
    
    


    
    
    process_node_data(node_data)

Solution (Python):
class Node(object):
    root = None

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

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

    @classmethod
    def walk_preorder(cls, node):
        """ ??????????????? """
        
        
        print(' {0}'.format(node.key), end='')
        if node.left != None:
            
            cls.walk_preorder(node.left)
        if node.right != None:
            
            cls.walk_preorder(node.right)
        

    @classmethod
    def walk_inorder(cls, node):
        """ ??????????????? """
        
        if node.left != None:
            
            cls.walk_inorder(node.left)
        
        print(' {0}'.format(node.key), end='')
        if node.right != None:
            
            cls.walk_inorder(node.right)
        

    def get_type(self):
        if self.parent:
            return 'root'
        elif self.left == None and self.right == None:
            return 'leaf'
        else:
            return 'internal node'

    def get_depth(self):
        if self.parent == None:
            return 0
        else:
            depth = 1
            t = self.parent
            while t.parent != None:
                t = t.parent
                depth += 1
            return depth

    def get_height(self):
        if self.height:
            return self.height
        h_left = 0
        h_right = 0
        if self.left != None:
            h_left = self.left.get_height() + 1
        if self.right != None:
            h_right = self.right.get_height() + 1
        self.height = max(h_left, h_right)
        return self.height

    def get_degree(self):
        degree = 0
        if self.left != None:
            degree += 1
        if self.right != None:
            degree += 1
        return degree

    def get_sibling(self):
        if self.parent == None:
            return -1
        p = self.parent
        if p.left != self and p.left != None:
            return p.left
        if p.right != self and p.right != None:
            return p.right


def process_node_data(node_data):
    for inst in node_data:
        if inst[0] == 'print':
            result = Node.walk_inorder(Node.root)
            print('')
            
            result = Node.walk_preorder(Node.root)
            
            print('')
        else:
            node_key = int(inst[1])
            new_node = Node(node_key)
            Node.insert(new_node)


def flatten(l):
    """ http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python """
    import collections
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el


if __name__ == '__main__':
    
    num_of_nodes = int(input())
    node_data = [input().split(' ') for _ in range(num_of_nodes)]
    
    
    
    
    
    
    

    
    
    process_node_data(node_data)

Solution (Python):
import sys

NIL = -1

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

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

    def insert(self, z):
        y = NIL
        x = self.root

        while x != NIL:
            y = x

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

        z.parent = y

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

    def inorder_walk(self, node):
        if node == NIL:
            return

        if node.left != NIL:
            self.inorder_walk(node=node.left)

        print(' ' + str(node.key), end='')

        if node.right != NIL:
            self.inorder_walk(node=node.right)

    def preorder_walk(self, node):
        if node == NIL:
            return

        print(' ' + str(node.key), end='')

        if node.left != NIL:
            self.preorder_walk(node=node.left)

        if node.right != NIL:
            self.preorder_walk(node=node.right)

    def show(self):
        self.inorder_walk(self.root)
        print()
        self.preorder_walk(self.root)
        print()


n = int(sys.stdin.readline())
T = Tree()

for i in range(n):
    line = sys.stdin.readline().split()
    
    if len(line) == 1:
        T.show()
    else:
        key = int(line[1])

        T.insert(Node(key))

Solution (Python):
import sys

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

    def prewalk(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.prewalk()
        if self.right:
            nodeList += self.right.prewalk()
        return nodeList

    def inwalk(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inwalk()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inwalk()
        return nodeList

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

    def insert(self, key):
        Nz = Node(key)
        Ny = None 
        Nx = self.root
        while Nx:
            Ny = Nx
            if Nz.key < Ny.key:
                Nx = Nx.left
            else:
                Nx = Nx.right
        Nz.parent = Ny
        if Ny == None:
            self.root = Nz
        elif Nz.key < Ny.key:
            Ny.left = Nz
        else:
            Ny.right = Nz

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

tree = Tree()

n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

Solution (Python):


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

            
            x = node
            x.parent = parent_candidate

            
            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:
            
            if found_node.is_leaf():
                
                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:
                
                if found_node.has_one_child():
                    one_child = found_node.get_one_child()

                    
                    one_child.parent = found_node.parent

                    
                    if found_node.parent.left == found_node:
                        found_node.parent.left = one_child
                    else:
                        found_node.parent.right = one_child

                
                else:
                    next_section_point = found_node.get_next_section_point()
                    
                    
                    key = next_section_point.key
                    self.delete(next_section_point.key)
                    found_node.key = key


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

    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()


def test():
    tree = Tree()
    values = []
    for _ in range(10):
        values.append(random.randint(0, 99))
    print(values)

    for v in values:
        node = Node(v)
        tree.insert(node)

    tree.print_inorder()
    print("")

    tree.print_preorder()
    print("")

    
    
    

    
    

    

    pass


def delete_test():
    tree = Tree()
    values = []
    for _ in range(10):
        values.append(random.randint(0, 99))
    values = list(set(values))
    print(values)

    for v in values:
        node = Node(v)
        tree.insert(node)
    

    print('delete', values[1])
    tree.delete(values[1])

    print('delete', values[3])
    tree.delete(values[3])

    tree.print_preorder()


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

    if 'print' in s:
        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))

Solution (Python):

class Tree:
    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None
        self.key = -1


def preparse(u):
    if u is None: return
    print(" ", end="")
    print(u.key, end="")
    preparse(u.left)
    preparse(u.right)


def inparse(u):
    if u is None: return
    
    inparse(u.left)
    
    print(" ", end="")
    print(u.key, end="")
    
    inparse(u.right)
    

def insert(key):
    global root
    y = None
    sch = root
    
    z = Tree()
    z.key = key

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

    
    z.parent = y

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

    
    trees.append(z)


def showresult():
    inparse(root)
    print("")
    preparse(root)
    print("")


N = int(input())

trees = []
root = None

for i in range(N):
    l = list(input().split())
    com = l[0]
    if com == "insert":
        key = int(l[1])
        
        insert(key)
    elif com == "print":
        showresult()

Solution (Python):
treeRoot = {'left': None, 'right': None, 'p': None, 'val': None}

root = None


def insert(val):
    global root
    z = {'left': None, 'right': None, 'p': None, 'val': val}
    x = root
    y = None
    while x:
        y = x
        if z['val'] < x['val']:
            x = x['left']
        else:
            x = x['right']
    z['p'] = y
    if y is None:
        root = z
    else:
        if z['val'] < y['val']:
            y['left'] = z
        else:
            y['right'] = z


def inorder(root):
    if root is None:
        return
    inorder(root['left'])
    print(' ', end='')
    print(root['val'], end='')
    inorder(root['right'])


def preorder(root):
    if root is None:
        return
    print(' ', end='')
    print(root['val'], end='')
    preorder(root['left'])
    preorder(root['right'])


M = int(input())
for _ in range(M):
    line = input().strip()
    if line == 'print':
        inorder(root)
        print('')
        preorder(root)
        print('')
    else:
        inst, k = line.split()
        k = int(k)
        if inst == 'insert':
            insert(k)
        elif inst == 'find':
            pass
        elif inst == 'delete':
            pass

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

    def insert(self, val):
        if self.v is None:
            self.v = val
            return
        n = Node(val)
        cur_node = self
        prev_node = None
        while cur_node:
            prev_node = cur_node
            if val < prev_node.v:
                cur_node = prev_node.l
            else:
                cur_node = prev_node.r
        if prev_node is None:
            self.v = n.v
        else:
            if val < prev_node.v:
                prev_node.l = n
            else:
                prev_node.r = n

    def __str__(self):
        return str(self.v)

    def preorder(self):
        if self.v:
            print(' {0}'.format(self.v), end='')
        if self.l:
            self.l.preorder()
        if self.r:
            self.r.preorder()

    def inorder(self):
        if self.l:
            self.l.inorder()
        if self.v:
            print(' {0}'.format(self.v), end='')
        if self.r:
            self.r.inorder()


M = int(input())
tree = Node()
for _ in range(M):
    line = input().strip()
    if line == 'print':
        tree.inorder()
        print('')
        tree.preorder()
        print('')
    else:
        inst, k = line.split()
        k = int(k)
        if inst == 'insert':
            tree.insert(k)
        elif inst == 'find':
            pass
        elif inst == 'delete':
            pass

Solution (Python):
class Node():
    key = 0
    l = None
    r = None
    def __init__(self, key):
        self.key = key
T = [None] * 5000005
def insert(z):
    if z == 0: return
    y = 0
    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[i] = Node(x)
        insert(i)

Solution (Python):
import sys
class BinaryTree:
    def __init__(self):
        self.root = None
    def b_insert(self,x):
        if self.root is None:
            self.root = Node(x)
            return
        node = None
        root = self.root
        while root is not None:
            node = root
            if x == root.data:
                return
            elif x < root.data:
                root = root.left
            else:
                root = root.right
        if node is None:
            
            node = Node(x)
        elif node.data < x:
            
            node.right = Node(x)
        else:
            
            node.left = Node(x)
    def b_inorder(self):
        return inorder(self.root)
    def b_preorder(self):
        return preorder(self.root)
         
class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None
             

def inorder(node):
    nodelist = []
    if node.left:
        nodelist += inorder(node.left)
    nodelist += [node.data]
    if node.right:
        nodelist += inorder(node.right)
    return nodelist
def preorder(node):
    nodelist = [node.data]
    if node.left:
        nodelist += preorder(node.left)
    if node.right:
        nodelist += preorder(node.right)
    return nodelist
 
line = sys.stdin.readline()
bfs = BinaryTree()
 
for temp in sys.stdin:
    if temp[0] == 'i':
        command,num = (n for n in temp.split(" "))
        bfs.b_insert(int(num))
    else:
        print("",end=" ")
        print(*bfs.b_inorder())
        print("",end=" ")
        print(*bfs.b_preorder())

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

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

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

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

def print_inorder(node):
  if node is None: return
  print_inorder(node.left)
  print(" {}".format(node.key), end="")
  print_inorder(node.right)

def print_preorder(node):
  if node is None: return
  print(" {}".format(node.key), end="")
  print_preorder(node.left)
  print_preorder(node.right)

T = BinarySearchTree()
for i in range(int(input())):
  params = input().split()
  if params[0] == "insert":
    T.insert(Node(int(params[1])))
  if params[0] == "print":
    print_inorder(T.root)
    print("")
    print_preorder(T.root)
    print("")

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

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

    def show(self):
        print(" ", end="")
        print(*list(map(str, self.root.inwalk())))
        print(" ", end="")
        print(*list(map(str, self.root.prewalk())))


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

    def prewalk(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.prewalk()
        if self.right:
            nodeList += self.right.prewalk()
        return nodeList

    def inwalk(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inwalk()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inwalk()
        return nodeList


tree = Tree()
P = []
I = []
n = int(input())
for i in range(n):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        tree.insert(int(cmd[1]))
    else:
        tree.show()