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):
n = int(input())

class Node:
    def __init__(self):
        self.key = -1
        self.parent_id = -1
        self.left_id = -1
        self.right_id = -1


def insert(nodes,z):
    y = -1
    root_id = -1
    for i in range(len(nodes)):
        if nodes[i].parent_id == -1:
            root_id = i
            break

    x = root_id

    while x != -1:
        y = x
        if z.key < nodes[x].key:
            x = nodes[x].left_id
        else:
            x = nodes[x].right_id

    z.parent_id = y
    nodes.append(z)
    z_id = len(nodes) - 1
    if y == -1: pass
    elif z.key < nodes[y].key:
        nodes[y].left_id = z_id
    else:
        nodes[y].right_id = z_id


def pre(node_id):
    pre_list.append(nodes[node_id].key)
    left = nodes[node_id].left_id
    right = nodes[node_id].right_id

    if left != -1:
        pre(left)
    if right != -1:
        pre(right)


def Ino(node_id):
    if nodes[node_id].left_id != -1 :
        Ino(nodes[node_id].left_id)
    ino_list.append(nodes[node_id].key)
    if nodes[node_id].right_id != -1:
        Ino(nodes[node_id].right_id)

nodes = []
for i in range(n):
    cmd = input()
    op = cmd[0]

    if op == "i":
        z = Node()
        number = int(cmd[7:])
        z.key = number

        insert(nodes,z)

    if op =="p":
        pre_list = []
        ino_list = []
        for i in range(len(nodes)):
            if nodes[i].parent_id == -1:
                Ino(i)
                pre(i)
                break


        pre_list = list(map(str, pre_list))
        ino_list = list(map(str, ino_list))
        print(" ", end="")
        print(' '.join(ino_list))
        print(" ", end="")
        print(' '.join(pre_list))

Solution (Python):
from sys import stdin
N=int(input())
nodes=[None]*N
class node_tree():
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.brother=None
        self.up=None

def ino(u):

    if u.left is not None:
        ino(u.left)
    print("",u.node,end="")
    if u.right is not None:
        ino(u.right)
def pre(u):
    print("",u.node,end="")
    if u.left is not None:
        pre(u.left)
    if u.right is not None:
        pre(u.right)
def search(u,key):
    if u.node <=key.node:
        if u.right is not None:
            search(u.right,key)
        else:u.right=key
    else:
        if u.left is not None:
            search(u.left,key)
        else:u.left=key
for i in range(N):
    command= list((stdin.readline().strip().split()))
    if len(command)!=1:
        key=int(command[1])
        if i==0:
            nodes[i]=node_tree(key)
        else:
            ins=node_tree(key)
            search(nodes[0],ins)
            nodes[i]=ins
    else:
        ino(nodes[0])
        print()
        pre(nodes[0])
        print()

Solution (Python):
n = int(input())
inst_k = [-1]*n
inst = [-1]*n
for i in range(n):
    tmp = input().split()
    inst[i] = tmp[0]
    if len(tmp) == 2:
        inst_k[i] = int(tmp[1])

class BST:
    def __init__(self):
        self.key = []
        self.parent = []
        self.left_child = []
        self.right_child = []
        self.root = -1

    def insert(self,new_key):
        new_node = len(self.key)
        self.key.append(new_key)
        self.left_child.append(-1)
        self.right_child.append(-1)
        self.parent.append(-1)

        searching_node = self.root
        searching_node_parent = -1
        while searching_node != -1:
            searching_node_parent = searching_node
            if new_key < self.key[searching_node]:
                searching_node = self.left_child[searching_node]
            else:
                searching_node = self.right_child[searching_node]
        if searching_node_parent == -1:
            self.root = new_node
        else:
            self.parent[new_node] = searching_node_parent
            if new_key < self.key[searching_node_parent]:
                self.left_child[searching_node_parent] = new_node
            else:
                self.right_child[searching_node_parent] = new_node
    
    def print_clear(self):
        self.preorder_ans = []
        self.inorder_ans = []
    
    def preorder(self,node):
        if node != -1:
            self.preorder_ans.append(self.key[node])
            self.preorder(self.left_child[node])
            self.preorder(self.right_child[node])
    
    def inorder(self,node):
        if node != -1:
            self.inorder(self.left_child[node])
            self.inorder_ans.append(self.key[node])
            self.inorder(self.right_child[node])

tree = BST()
for i in range(n):
    if inst[i] == "insert":
        tree.insert(inst_k[i])
    elif inst[i] == "find":
        pass
    elif inst[i] == "print":
        tree.print_clear()
        tree.preorder(tree.root)
        tree.inorder(tree.root)
        print(" ",end = "")
        print(*tree.inorder_ans)
        print(" ",end = "")
        print(*tree.preorder_ans)

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

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        x, y = self.root, None
        z = Node()
        z.key = key
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    
    def preOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        print("", r.key, end = '')
        self.preOrder(r.left)
        self.preOrder(r.right)
    
    def inOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        self.inOrder(r.left)
        print("", r.key, end = '')
        self.inOrder(r.right)

tree = BST()
for _ in range(int(input())):
    s = input()
    if s[0] == 'i':
        tree.insert(int(s[7:]))
    else:
        tree.inOrder()
        print("")
        tree.preOrder()
        print("")

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

T = {}
root = None

def insert_node(key):
    global root
    x = root
    y = None
    z = Node(None, None, None)
    while x != None:
        y = x
        if key < x:
            x = T[x].left
        else:
            x = T[x].right
    z.parent = y
    if y == None:
        root = key
    else:
        if key < y:
            T[y].left = key
        else:
            T[y].right = key
    T[key] = z

def in_print(key, ls):
    if key == None:
        return
    in_print(T[key].left, ls)
    ls.append(key)
    in_print(T[key].right, ls)

def pre_print(key, ls):
    if key == None:
        return
    ls.append(key)
    pre_print(T[key].left, ls)
    pre_print(T[key].right, ls)

def print_node():
    in_ls, pre_ls = [], []
    in_print(root, in_ls)
    pre_print(root, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)

N = int(input())
for i in range(N):
    com = input().split()
    if com[0] == 'insert':
        insert_node(int(com[1]))
    elif com[0] == 'print':
        print_node()

Solution (Python):


Node = list()
n = int(input())

def insertKey(k):
    idx = len(Node)
    Node.append([k, -1, -1])
    if idx > 0:
        pPrv = -1
        pTmp = 0
        while pTmp != -1:
            pPrv = pTmp
            if k < Node[pTmp][0]:
                pTmp = Node[pTmp][1]
            else:
                pTmp = Node[pTmp][2]
        if Node[-1][0] < Node[pPrv][0]:
            Node[pPrv][1] = idx
        else:
            Node[pPrv][2] = idx

def inOrder(num):
    if num == -1:
        return
    inOrder(Node[num][1])
    print(' {}'.format(Node[num][0]), end = '')
    inOrder(Node[num][2])

def preOrder(num):
    if num == -1:
        return
    print(' {}'.format(Node[num][0]), end = '')
    preOrder(Node[num][1])
    preOrder(Node[num][2])

for i in range(n):
    temp = input().strip()
    if temp[:6] == 'insert':
        insertKey(int(temp[7:]))
    else:
        inOrder(0)
        print('')
        preOrder(0)
        print('')

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

    def insert(self,t,key):
        '''
        if self.key==None:self.key = key
        elif key<self.key:
            if self.left == None:self.left = Node(key)
            else                :self.left.insert(key)
        else:
            if self.right == None:self.right = Node(key)
            else                 :self.right.insert(key)
        '''
        if t.key == None:
            t.key = key
            return
        y = None 
        x = t
        while x is not None:
            y = x
            if key<x.key:x = x.left
            else        :x = x.right

        if y is None  :t = Node(key)
        elif key<y.key:y.left = Node(key)
        else          :y.right = Node(key)

    def inorder(self):
        if self.left!=None:self.left.inorder()
        print (' %d'%self.key,end = '')
        if self.right!=None:self.right.inorder()

    def preorder(self):
        print (' %d'%self.key,end = '')
        if self.left!=None:self.left.preorder()
        if self.right!=None:self.right.preorder()

    def walk(self):
        self.inorder()
        print ()
        self.preorder()
        print ()

def main():
    Tree = Node()
    q = int(input())
    for _ in range(q):
        com = list(input().split())
        if com[0] == 'insert':
            Tree.insert(Tree,int(com[1]))
        else :
            Tree.walk()


if __name__ == '__main__':
    main()

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


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

    def __init__(self):
        self.root = None

    def insert(self, target_key):
        parent = None
        attention = self.root
        target = self.Node(target_key)

        while attention is not None:
            parent = attention
            if target.key < attention.key:
                attention = attention.left
            else:
                attention = attention.right
        target.parent = parent

        if parent is None:
            self.root = target
        elif target.key < parent.key:
            parent.left = target
        else:
            parent.right = target

    def preorder_walk(self, node):
        if node is None:
            return []
        return [node.key] + self.preorder_walk(node.left) + self.preorder_walk(node.right)

    def inorder_walk(self, node):
        if node is None:
            return []
        return self.inorder_walk(node.left) + [node.key] + self.inorder_walk(node.right)


N = int(my_input())
BST = BinarySearchTree()
for _ in range(N):
    command = my_input().split()
    if len(command) == 2:
        BST.insert(int(command[1]))
    else:
        print(' ' + ' '.join(map(str, BST.inorder_walk(BST.root))))
        print(' ' + ' '.join(map(str, BST.preorder_walk(BST.root))))

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

class BST():
  def __init__(self):
    self.T = list()
    self.root = None
    self.res = []

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

  def preorder(self,node:Node):
    if node is None:
      return
    
    print(" " + str(node.key), end="")
    self.preorder(node.left)
    self.preorder(node.right)

  def inorder(self, node:Node):
    if node is None:
      return
    self.inorder(node.left)
    print(" " + str(node.key), end="")
    self.res.append(node.key)
    self.inorder(node.right)




def main():
  n = int(input())
  T = BST()
  for _ in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
      key = int(cmd[1])
      T.insert(Node(key))
    else:

      T.inorder(T.root)
      print()


      T.preorder(T.root)
      print()


if __name__ == "__main__":
  import sys, io

  main()

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

def insert(k):
    y = -1
    x = root[0]
    z = len(T)
    T.append(Node())
    T[z].key = k
    while x != -1:
        y = x
        if T[z].key < T[x].key: x = T[x].l
        else: x = T[x].r
    T[z].p = y
    if y == -1: root[0] = z
    elif T[z].key < T[y].key: T[y].l = z
    else: T[y].r = z

def inorder(u):
    if u == -1: return
    inorder(T[u].l)
    print(" {}".format(T[u].key),end="")
    inorder(T[u].r)

def preorder(u):
    if u == -1: return
    print(" {}".format(T[u].key),end="")
    preorder(T[u].l)
    preorder(T[u].r)

m = int(input())
T = []
root = [-1]
for _ in range(m):
    comm = input().split()
    if comm[0] == "insert":
        insert(int(comm[1]))
    else:
        inorder(root[0])
        print("")
        preorder(root[0])
        print("")

Solution (Python):



class Node():

    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None
    
    def __repr__(self):
        return str(self.k)


def insert(z):
    if z == T[0]:
        return
    y = None
    x = T[0]
    while x != None:
        y = x 
        if z.k < y.k:
            x = y.l
        else:
            x = y.r
    z.p = y

    if z.k < y.k:
        y.l = z
    else:
        y.r = z


def preparse(u):
    print(" ", u.k, sep="", end="")
    if u.l != None:
        preparse(u.l)
    if u.r != None:
        preparse(u.r)


def inparse(u):
    if u.l != None:
        inparse(u.l)
    print(" ", u.k, sep="", end="")
    if u.r != None:
        inparse(u.r)


m = int(input())
T = [None for i in range(m)]
for id in range(m):
    cmd = input().split()
    if cmd[0] == "insert":
        T[id] = Node(int(cmd[1]))
        insert(T[id])
    elif cmd[0] == "print":
        inparse(T[0])
        print()
        preparse(T[0])
        print()

Solution (Python):
import sys

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

root = None

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

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

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

Solution (Python):
def resolve():
    '''
    code here
    '''
    N = int(input())
    queries = [input().split() for _ in range(N)]

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

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

        def insert(self, val):
            if self.root == None:
                self.root = Node(val)
                
            else:
                
                node = self.root
                is_search = True
                while is_search:
                    
                    if val <= node.val:
                        if node.left:
                            node = node.left
                        else:
                            node.left = Node(val)
                            is_search = False
                    else:
                        if node.right:
                            node = node.right
                        else:
                            node.right = Node(val)
                            is_search = False


        def show_inorder(self, node):
            if node == None:
                return

            self.show_inorder(node.left)
            print('', node.val, end='')
            self.show_inorder(node.right)


        def show_preorder(self, node):
            if node == None:
                return

            print('', node.val, end='')
            self.show_preorder(node.left)
            self.show_preorder(node.right)

    bt = BinaryTree()

    for query, *val in queries:
        if query == 'insert':
            value = int(val[0])
            bt.insert(value)
        else:
            bt.show_inorder(bt.root)
            print('')
            bt.show_preorder(bt.root)
            print('')



if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
sys.setrecursionlimit(10**6)


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

    def __repr__(self):
        k = str(self.key)
        p = str(self.parent.key) if self.parent else 'None'
        l = str(self.left.key) if self.left else 'None'
        r = str(self.right.key) if self.right else 'None'
        s = "<Node %s: parent=%s, left=%s, right=%s>" % (k, p, l, r)
        return s


class BinaryTree():
    def __init__(self, n=0):
        self.T = [Node() for _ in range(n)]
        self.root = None

    def preorder(self):
        self.preorder_key = []
        self.preorder_rec(self.root)
        print('', *(self.preorder_key))

    def preorder_rec(self, node):
        if node == None:
            return
        self.preorder_key.append(node.key)
        self.preorder_rec(node.left)
        self.preorder_rec(node.right)

    def inorder(self):
        self.inorder_key = []
        self.inorder_rec(self.root)
        print('', *(self.inorder_key))

    def inorder_rec(self, node):
        if node == None:
            return
        self.inorder_rec(node.left)
        self.inorder_key.append(node.key)
        self.inorder_rec(node.right)

    def insert(self, key):
        node = Node(key)

        y = None
        x = self.root

        while x != None:
            y = x
            if key < x.key:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif key < y.key:
            y.left = node
        else:
            y.right = node


N = int(input())
S = [input() for _ in range(N)]
tree = BinaryTree()

for s in S:
    if 'print' in s:
        tree.inorder()
        tree.preorder()
    else:
        _, key = s.split()
        tree.insert(int(key))

Solution (Python):
class node(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.value = None
        self.parent = None

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

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


def preorder(node):
    if node is None:
        return 
    print(" "+str(node.value),end="")    
    preorder(node.left)
    preorder(node.right)
    

def inorder(node):
    if node is None:
        return 
    inorder(node.left)
    print(" "+str(node.value),end="")
    inorder(node.right)
    
def print_all_node(root):
    stack = [root]
    while stack:
        node = stack.pop()
        print("p: ",node.parent,"r:",node.right,"l:",node.left)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

if __name__ == "__main__":
    n = int(input())
    T = Tree()
    queries = [input().split() for _ in range(n)]
    for query in queries:
        if query[0] == "print":
            
            inorder(T.root)
            print("")
            preorder(T.root)
            print("")

        else:
            command,value = query
            node_z = node()
            node_z.value = int(value)
            if command == "insert":
                insert(T,node_z)

Solution (Python):
import sys


class Node():

	def __init__(self,id,key):
		
		self.id = id
		self.key = key
		self.root = -1
		self.left = -1
		self.right = -1
		self.parent = -1
		self.sibling = -1
		self.degree = 0
		self.depth = 0
		self.height = 0

def print_nodes(Nodes,node_id,type,output):

	
	
	
	

	if node_id == -1:
		return

	if type == 0:
		output.append(Nodes[node_id].key)

	print_nodes(Nodes,Nodes[node_id].left,type,output)
	if type == 1:
		output.append(Nodes[node_id].key)
	print_nodes(Nodes,Nodes[node_id].right,type,output)
	if type == 2:
		output.append(Nodes[node_id].key)

def insert(T,z):

	if len(T) == 1:
		return


	y = -1
	x = T[0]

	while True:
		y = x
		if z.key < x.key:
			if x.left == -1:
				break
			else:
				x = T[x.left]
		else:
			if x.right == -1:
				break
			else:
				x = T[x.right]

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

def test():

	n = int(sys.stdin.readline())
	T = [Node(0,0)] * n
	root = 0
	id = 0

	for i in range(n):

		inputs = sys.stdin.readline().split()

		if inputs[0] == "insert":
			if id == 0:
				T[id] = Node(id,int(inputs[1]))
				id += 1
				continue

			key = int(inputs[1])
			tmp_node = Node(id,key)
			T[id] = tmp_node
			insert(T,tmp_node)
			id += 1

		if inputs[0] == "print":
			output = []
			
			print_nodes(T,T[0].id,1,output)
			for j in range(len(output)-1):
				print(f" {output[j]}",end = '')
			print(f" {output[j+1]}")

			
			output2 = []
			print_nodes(T,T[0].id,0,output2)
			for j in range(len(output2)-1):
				print(f" {output2[j]}",end = '')
			print(f" {output2[j+1]}")

if __name__ == "__main__":
	test()

Solution (Python):

import sys
n = int(input())
class Node:
  def __init__(self,v):
    self.p = None
    self.key = v
    self.left = None
    self.right = None

sys.setrecursionlimit(1500)
r = None
def insert(z):
  global r
  y = None
  x = r
  while x != None:
    y = x
    if z.key < x.key:
      x = x.left
    else:
      x = x.right
  z.p = y

  if y == None:
    r = z
  elif z.key < y.key:
    y.left = z
  else:
    y.right = z

ret = []
def inorder(r):
  if r == None: return
  inorder(r.left)
  ret.append(r.key)
  inorder(r.right)

def preorder(r):
  if r == None: return
  ret.append(r.key)
  preorder(r.left)
  preorder(r.right)

for i in range(n):
  s = input()
  if s[0]=="i":
    insert(Node(int(s.split()[1])))
  else:
    ret = []
    inorder(r)
    print(""," ".join(map(str,ret)))
    ret = []
    preorder(r)
    print(""," ".join(map(str,ret)))

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

root = None

def insert(r, 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 Inorder_TreeWalk(node):
    if node is None:
        return

    Inorder_TreeWalk(node.left)
    print(" " + str(node.key), end="")
    Inorder_TreeWalk(node.right)

def Preorder_TreeWalk(node):
    if node is None:
            return
            
    print(" " + str(node.key), end="")
    Preorder_TreeWalk(node.left)
    Preorder_TreeWalk(node.right)

def Main():
    
    n = int(input())
    global root

    for i in range(n):
        inp = input().split()
        ope = inp[0]

        if ope == "insert":
            insert(root, node(int(inp[1]), None, None, None))

        elif ope == "print":
            Inorder_TreeWalk(root)
            print()
            Preorder_TreeWalk(root)
            print()
        else:
            pass
Main()

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


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

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            parent = None
            cur = self.root
            while cur:
                parent = cur
                if val < cur.val:
                    cur = cur.left
                elif cur.val < val:
                    cur = cur.right

            if val < parent.val:
                parent.left = TreeNode(val)
            elif parent.val < val:
                parent.right = TreeNode(val)

    def remove(self, val):
        self._remove(self.root, val, None)

    def _remove(self, node, val, parent):
        if not node:
            return
        elif val < node.val:
            self._remove(node.left, val, node)
        elif node.val < val:
            self._remove(node.right, val, node)
        else:
            if node.left and node.right:
                
                cur = node.right
                while cur.left:
                    cur = cur.left
                node.val = cur.val
                self._remove(node.right, cur.val, node)
            elif node.left:
                if parent.left == node:
                    parent.left = node.left
                elif parent.right == node:
                    parent.right = node.left
            elif node.right:
                if parent.left == node:
                    parent.left = node.right
                elif parent.right == node:
                    parent.right = node.right
            else:
                if parent.left == node:
                    parent.left = None
                elif parent.right == node:
                    parent.right = None


def inorder(node):
    if node:
        res = []
        res += inorder(node.left)
        res.append(node.val)
        res += inorder(node.right)
        return res
    else:
        return []


def preorder(node):
    if node:
        res = [node.val]
        res += preorder(node.left)
        res += preorder(node.right)
        return res
    else:
        return []


if __name__ == '__main__':
    n = int(input())
    bst = BinarySearchTree()
    for _ in range(n):
        op = input().split()
        if len(op) == 2:
            bst.insert(int(op[1]))
        else:
            for x in inorder(bst.root):
                print(f' {x}', end='')
            print()
            for x in preorder(bst.root):
                print(f' {x}', end='')
            print()