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):
class Tree:
    def __init__(self, orders):
        self.root = None
        for order in orders:
            if len(order) == 1:
                self.inorder_print()
                self.preorder_print()
            else:
                self.insert(int(order[1]))

    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 not y:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def inorder_print(self):
        self.root.inorder_print()
        print()

    def preorder_print(self):
        self.root.preorder_print()
        print()


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

    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(' {}'.format(self.key), end='')
        if self.right:
            self.right.inorder_print()

    def preorder_print(self):
        print(' {}'.format(self.key), end='')
        if self.left:
            self.left.preorder_print()
        if self.right:
            self.right.preorder_print()


if __name__ == '__main__':
    import sys
    m = int(input())
    orders = [line.strip().split() for line in sys.stdin]
    
    Tree(orders)

Solution (Python):
class NullNode():
    def __init__(self):
        self.id = None

null_node = NullNode()
class Node():
    def __init__(self, id):
        global null_node
        self.id = id
        self.parent = null_node
        self.left = null_node
        self.right =  null_node

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

def delete(id, root_node):
    
    global null_node
    type = ''
    node = root_node
    node_parent = null_node
    while node.id != id:
        node_parent = node
        if id < node.id:
            node = node.left
            type = 'L'
        else:
            node = node.right
            type = 'R'
    if node.right is not None:
        node.right.parent = node_parent
    elif node.left is not None:
        node.left.parent = node_parent
    else:
        node.parent = null_node

    if type == 'L':
        node_parent.left = null_node
    else:
        node_parent.right = null_node

import sys






n = int(sys.stdin.readline())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    elif command == 'delete':
        id = int(input_line[1])
        delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        out = ' ' + ' '.join(inorder_list)
        print(out)
        out = ' ' + ' '.join(preorder_list)
        print(out)

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

    def preorder(self):
        ret = [self.key]
        if self.left:
            ret += self.left.preorder()
        if self.right:
            ret += self.right.preorder()
        return ret

    def inorder(self):
        ret = []
        if self.left:
            ret += self.left.inorder()
        ret += [self.key]
        if self.right:
            ret += self.right.inorder()
        return ret


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

    def insert(self, k):
        z = Node(k)
        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 print(self):
        print('', ' '.join(map(str, self.root.inorder())))
        print('', ' '.join(map(str, self.root.preorder())))


m = int(input())
tree = Tree()
for _ in range(m):
    s = input().split()
    if s[0] == "insert":
        tree.insert(int(s[1]))
    else:
        tree.print()

Solution (Python):

N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(root):
    x = root
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(root):
    x = root
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

root = None
for data in trees:
    if data[0] == "insert":
        z = BinaryTree(int(data[1]))
        root = Insert(root,z)
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " " + " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " " + " ".join([str(num) for num in preList])
        print(a)

Solution (Python):
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Solution (Python):

from __future__ import division, print_function
from sys import stdin


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


def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)


def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)


n = int(stdin.readline())


top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

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

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

def pre_parse(T: dict, u: int, pre_ls: list):
    if u is None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)
    pre_parse(T, T[u].right, pre_ls)

def in_parse(T: dict, u: int, in_ls: list):
    if u is None:
        return
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T: dict, ROOT: int , z: int):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()
        x = ROOT
        while x is not None: 
            next_parent = x
            if z < x: 
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        if z < next_parent: 
            T[next_parent].left = z
        else:
            T[next_parent].right = z

def find(T: dict, ROOT: int, k: int):
    """
    Tからkを見つけ出す。見つからなかったらNoneを返す
    """
    x = ROOT
    while x is not None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T: dict, z: int):
    
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError
        del T[z]
    
    
    elif T[z].right is None:
        
        is_z_left = True if T[parent].left == z else False
        child = T[z].left
        if is_z_left: 
            T[parent].left = child
        else: 
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif T[z].left is None:
        
        is_z_left = True if T[parent].left == z else False
        child = T[z].right
        if is_z_left: 
            T[parent].left = child
        else: 
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        
        node_next_more = get_min_descendants(T, T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        
        if parent is None:
            if node_next_more == right:
                T[right].parent = None
                T[right].left = left
                ROOT = right
                del T[z]
                return
            else:
                
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more 
                T[right].parent = node_next_more 
                
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return
        
        else: 
            is_z_left = True if T[parent].left == z else False
            if node_next_more == right:
                
                if is_z_left:
                    T[parent].left = right
                else:
                    T[parent].right = right
                T[right].parent = parent
                T[right].left = left
                del T[z]
                return
            else:
                
                if is_z_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more
                
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more 
                T[right].parent = node_next_more 
                
                
                
                
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return

def get_min_descendants(T:dict, z:int):
    x = z
    while T[x].left is not None:
        x = T[x].left
    return x

def print_result(T: dict, ROOT: int):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print("", *in_ls)
    print("", *pre_ls)

def main():
    N = int(input())
    T = {}
    ROOT = 0
    for i in range(N):
        tmp = input().split()
        if tmp[0] == "insert":
            value = int(tmp[1])
            if i==0:
                ROOT = value
            insert(T, ROOT, value)
        elif tmp[0] == "find":
            value = int(tmp[1])
            if find(T, ROOT, value):
                print("yes")
            else:
                print("no")
        elif tmp[0] == "delete":
            value = int(tmp[1])
            delete_node(T, value)
        else:
            print_result(T, ROOT)

main()

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

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

def pre_parse(T:dict, u: int, pre_lis: list):
    if u == None:
        return
    pre_lis.append(u)
    pre_parse(T, T[u].left, pre_lis)
    pre_parse(T, T[u].right, pre_lis)

def in_parse(T,u,in_lis):
    if u == None:
        return
    in_parse(T, T[u].left, in_lis)
    in_lis.append(u)
    in_parse(T, T[u].right, in_lis)

def insert(T, Root, z):
    
    
    
    if Root == z:
        T[z] = Node()
    
    else:
        T[z] = Node()
        x = Root
        while x is not None:
            
            next_parent = x
            if x > z:
                x = T[x].left
                temp = 1
            else:
                x = T[x].right
                temp = 2

        T[z].parent = next_parent
        if temp == 1:
            T[next_parent].left = z
        else:
            T[next_parent].right = z

def find(T,Root,k):
    
    x = Root
    while x != None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T,z):
    
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError("something wrong in case 1")

        del T[z]

    
    elif T[z].right is None:
        
        
        z_is_left = True if T[parent].left == z else False
        child = T[z].left
        if z_is_left:
            T[parent].left = child
            T[child].parent = parent
            del T[z]
        else:
            T[parent].right = chile
            T[child].parent = parent
            del T[z]

    elif T[z].left is None:
        z_is_left = True if T[parent].left == z else False
        child = T[z].right
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]

    
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        
        node_next_more = get_min_in_descendants(T,T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        
        if parent is None:
            if node_next_more == right:
                
                T[right].parent = None
                T[right].left = left
                Root = right
                del T[z]
                return

            else:
                
                
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more
                T[right].parent = node_next_more
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                    T[next_more_parent].left = next_more_right
                Root = node_next_more
                del T[z]
                return

        else:
            
            
            z_is_left = True if T[parent].left == z else False
            if node_next_more == right:
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                T[node_next_more].parent = parent
                T[node_next_more].left = left
                del T[z]
                return
            else:
                
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                
                T[node_next_more].left = T[z].left
                T[node_next_more].right = T[z].right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more
                T[right].parent = node_next_more

                T[next_more_parent].left = next_more_right
                if T[next_more_right] is not None:
                    T[next_more_right].parent = next_more_parent

                del T[z]
                return

def get_min_in_descendants(T,z):
    x = z
    while T[x].left is not None:
        x = T[x].left

    return x

def print_result(T):
    pre_ls = []
    in_ls = []
    in_parse(T,Root,in_ls)
    pre_parse(T,Root,pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

N = int(input())
T = {}
for i in range(N):
    tmp = input()
    if tmp.startswith('print'):
        print_result(T)
    elif tmp.startswith('insert'):
        z = int(tmp.split()[1])
        if i == 0:
            Root = z
        insert(T,Root,z)
    elif tmp.startswith('find'):
        z = int(tmp.split()[1])
        if find(T,Root,z) is None:
            print('no')
        else:
            print('yes')
    elif tmp.startswith('delete'):
        z = int(tmp.split()[1])
        delete_node(T,z)

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

NIL = -1

m = int(input())

root = NIL

def insert(k):
    global root
    y = NIL
    x = root
    z = {'key':k, 'left':NIL, 'right':NIL}
    while x != NIL:
        y = x
        if z['key'] < x['key']:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y

    if y == NIL:
        root = z
    elif z['key'] < y['key']:
        y['left'] = z
    else:
        y['right'] = z

def inorder(u):
    if u == NIL:
        return
    inorder(u['left'])
    print(' ' + str(u['key']), end='')
    inorder(u['right'])

def preorder(u):
    if u == NIL:
        return
    print(' ' + str(u['key']), end='')
    preorder(u['left'])
    preorder(u['right'])

for _ in range(m):
    command = input()
    if command[:6] == 'insert':
        _, x = command.split()
        x = int(x)
        insert(x)
    else:
        inorder(root)
        print('')
        
        preorder(root)
        print('')

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

rt = None


def inorder(node):
    return inorder(node.left) + f' {node.data}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.data}' + preorder(node.left) + preorder(node.right) if node else ''



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

n = int(input())
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(rt)); print(preorder(rt))

Solution (Python):



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

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

def preorder(x):
    print(" "+str(x.key),end="")
    if x.left != None:
        preorder(x.left)
    if x.right != None:
        preorder(x.right)
        
def inorder(x):
    if x.left != None:
        inorder(x.left)
    print(" "+str(x.key),end="")
    if x.right != None:
        inorder(x.right)
    

root=None

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

Solution (Python):
class BinaryTree:
    class Node:
        def __init__(self, n):
            self.num = n
            self.parent = -1
            self.right = None
            self.left = None

    
    def __init__(self):
        self.root = None


    def insert(self, n):
        if not self.root:
            node = self.Node(n)
            self.root = node
        else:
            current, parent = self.root, None
            while current:
                parent = current
                if n < current.num:
                    current = current.left
                else:
                    current = current.right
            if n < parent.num:
                parent.left = self.Node(n)
            else:
                parent.right = self.Node(n)
            













    
    def print_preorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_preorder(node.right)
        elif not node.right:
            return [node.num] + self.print_preorder(node.left)
        else:
            return [node.num] + self.print_preorder(node.left) + self.print_preorder(node.right)


    def print_inorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_inorder(node.right)
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + [node.num] + self.print_inorder(node.right)


    def print_postorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return self.print_inorder(node.right) + [node.num]
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + self.print_inorder(node.right) + [node.num]



if __name__ == '__main__':
    n = int(input())
    qs = [ input().rstrip().split() for _ in range(n) ]
    bt = BinaryTree()
    for q in qs:
        if q[0] == 'insert':
            bt.insert(int(q[1]))
        elif q[0] == 'print':
            print(' ' + ' '.join(map(str,bt.print_inorder(bt.root))))
            print(' ' + ' '.join(map(str,bt.print_preorder(bt.root))))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class BinaryNode:
    def __init__(self, key, left=None, right=None):
        self.val = key
        self.left = left
        self.right = right


def insert(root, node):
    if root is None:
        root = node
    else:
        if root.val < node.val:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)
        else:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)


def preorder(root):
    ret = []
    if root is None: return ret
    ret.append(root.val)
    ret.extend(preorder(root.left))
    ret.extend(preorder(root.right))
    return ret


def inorder(root):
    ret = []
    if root is None: return ret
    ret.extend(inorder(root.left))
    ret.append(root.val)
    ret.extend(inorder(root.right))
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    s, key = sl()
    root = BinaryNode(int(key))

    for n in range(N - 1):
        input = sl()
        if input[0] == 'print':
            print("", *inorder(root))
            print("", *preorder(root))
        else:
            insert(root, BinaryNode(int(input[1])))


if __name__ == '__main__':
    main()

Solution (Python):





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

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.count = 0
    
    def insert(self, node: Node):
        self.count += 1
        if not self.root:
            self.root = node
            return

        cur = self.root
        while cur:
            if node.val > cur.val:
                if cur.right:
                    cur = cur.right
                    continue
                else:
                    cur.right,node.parent = node,cur
                    return
            else:
                if cur.left:
                    cur = cur.left
                    continue
                else:
                    cur.left,node.parent = node,cur
                    return


def main():

    
    preorder = []

    def preorder_walk(node):
        preorder.append(str(node.val))
        if node.left:
            preorder_walk(node.left)
        if node.right:
            preorder_walk(node.right)

    

    inorder = []

    def inorder_walk(node):
        if node.left:
            inorder_walk(node.left)
        inorder.append(str(node.val))
        if node.right:
            inorder_walk(node.right)


    n = int(input())
    
    bst = BinarySearchTree()
    
    for _ in range(n):
        op = input().strip().split()
        if op[0] == "insert":
            bst.insert(Node(int(op[1])))
        elif op[0] == "print":
            preorder,inorder = [],[]
            preorder_walk(bst.root)
            inorder_walk(bst.root)
            print(""," ".join(inorder))
            print(""," ".join(preorder))

if __name__ == "__main__":
    main()