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 TreeNode:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

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

  def insert(self, val):
    node = TreeNode(val)
    if self.root is None: 
      self.root = node
      return

    cur_parent = None
    cur_root = self.root

    while cur_root is not None:
      cur_parent = cur_root
      if val > cur_root.val:
        cur_root = cur_root.right
      else:
        cur_root = cur_root.left

    if val > cur_parent.val:
      cur_parent.right = node
    else:
      cur_parent.left = node

  def print(self):
    self.inorder = []
    self.preorder = []
    self.inorder_dfs(self.root)
    self.preorder_dfs(self.root)

    print(" " + " ".join([ str(i) for i in self.inorder ]))
    print(" " + " ".join([ str(i) for i in self.preorder ]))

  def inorder_dfs(self, root):
    if not root: return

    self.inorder_dfs(root.left)
    self.inorder.append(root.val)
    self.inorder_dfs(root.right)

  def preorder_dfs(self, root):
    if not root: return

    self.preorder.append(root.val)
    self.preorder_dfs(root.left)
    self.preorder_dfs(root.right)


n = int(input())
bst = Bst()
for _ in range(n):
  ins = list(map(str, input().split()))
  order = ins[0]
  if order == "insert":
    val = int(ins[1])
    bst.insert(val)
  elif order == "print":
    bst.print()

Solution (Python):
class Node:
    def __init__(self, id):
        self.id=id
        self.parent=self.left=self.right=None
        
    def insert(self, node):
        if node.id < self.id:
            if self.left is None:
                self.left=node
                node.parent=self
            else:
                self.left.insert(node)
        else:
            if self.right is None:
                self.right=node
                node.parent=self
            else:
                self.right.insert(node)
    
    def walk_inorder(self,result):
        if self.left:
            self.left.walk_inorder(result)
        result.append(self.id)
        if self.right:
            self.right.walk_inorder(result)
    
    def walk_preorder(self,result):
        result.append(self.id)
        if self.left:
            self.left.walk_preorder(result)
        if self.right:
            self.right.walk_preorder(result)
        

root=None
n=int(input())
for _ in range(n):
    cmd=input()
    if cmd[0]=='i':
        id=int(cmd.split()[1])
        node=Node(id)
        if root:
            root.insert(node)
        else:
            root=node
    else:
        if root:
            result=[]
            root.walk_inorder(result)
            print('',*result)
            result=[]
            root.walk_preorder(result)
            print('',*result)

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

def insert(key):
    global root
    
    if root.key is None:
        root.key = key
        return
    
    else:
        newNode = Node(key)
        x = root
        while x is not None:
            tmpParent = x
            if newNode.key < x.key:
                x = x.left
            else:
                x = x.right
        newNode.parent = tmpParent
        if newNode.key < tmpParent.key:
            tmpParent.left = newNode
        else:
            tmpParent.right = newNode

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.key)
    inorder(node.right, result)

def preorder(node, result):
    if node is None:
        return
    result.append(node.key)
    preorder(node.left, result)
    preorder(node.right, result)

def printOrderedResult(node, orderFunction):
    result = []
    orderFunction(node, result)
    result = [i for i in map(str, result)]
    print(' ', end='')
    print(' '.join(result))
    

root = Node()
n = int(input())

for i in range(n):
    command = input()
    try:
        command, key = command.split()
        key = int(key)
        insert(key)
    except ValueError:
        printOrderedResult(root, inorder)
        printOrderedResult(root, preorder)

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):
class node:
    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None
        self.key = None
        
class btree:
    def __init__(self):
        self.root = None
        
    def insert(self, v):
        y = None
        x = self.root
        z = node()
        z.key = v
        
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    

    def print_tree(self):
        def inorder(nd):
            if nd.left is not None:
                inorder(nd.left)
            print(' %i'%nd.key, end='')
            if nd.right is not None:
                inorder(nd.right)
        
        def preorder(nd):
            print(' %i'%nd.key, end='')
            if nd.left is not None:
                preorder(nd.left)
            if nd.right is not None:
                preorder(nd.right)
                
        inorder(self.root)
        print()
        preorder(self.root)
        print()
        
n = int(input())

bt = btree()

for i in range(n):
    inp = input()
    if inp.split()[0]=='insert':
        bt.insert(int(inp.split()[1]))
    else:
        bt.print_tree()

Solution (Python):

n = int(input())
COM = [list(input().split()) for _ in range(n)]

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

    def inorder(self,List):
        if self.data != None:
            if self.left != None:
                self.left.inorder(List)
            List.append(self.data)
            if self.right != None:
                self.right.inorder(List)
        return List

    def preorder(self,List):
        if self.data != None:
            List.append(self.data)
            if self.left != None:
                self.left.preorder(List)
            if self.right != None:
                self.right.preorder(List)
        return List

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

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

    def print(self):
        print(""," ".join(map(str,self.root.inorder([]))))
        print(""," ".join(map(str,self.root.preorder([]))))

btree = BTree()
cnt = 0
for i in range(n):
    if COM[i][0] == "insert":
        node = Node(int(COM[i][1]))
        btree.insert(node)
        cnt += 1
    else:
        btree.print()

Solution (Python):
class STNode:
    def __init__(self, k, l, r):
        self.key = k
        self.left = l
        self.right = r

def STinsert(h, z):
    p = None
    while True:
        if h.key == -1:
            break
        p = h
        if z.key < h.key:
            h = h.left
        else:
            h = h.right
    
    if z.key < p.key:
        p.left = z
    else:
        p.right = z
    
def preorder(head, h, A):
    if h.key == -1:
        return 
    A.append(h.key)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.key == -1:
        return 
    inorder(head, h.left, B)
    B.append(h.key)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

n = int(input())
NULLnode = STNode(-1, None, None)

first = list(input().split())
head = STNode(int(first[1]), NULLnode, NULLnode)
for i in range(n-1):
    temp = list(input().split())
    if temp[0] == 'insert':
        z = STNode(int(temp[1]), NULLnode, NULLnode)
        STinsert(head, z)
    else:
        A = []
        B = []
        inorder(head, head, B)
        preorder(head, head, A)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    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[:5] == 'print':
            inorder(root)
            print('')
            preorder(root)
            print('')
        else:

            _, k = command.split()
            k = int(k)
            insert(k)

Solution (Python):
def preParse(u):
    if u == None:
        return
    print(' {}'.format(u), end='')
    preParse(nodes[u][1])
    preParse(nodes[u][2])

def inParse(u):
    if u == None:
        return
    inParse(nodes[u][1])
    print(' {}'.format(u), end='')
    inParse(nodes[u][2])

nodes = {}



N = int(input())

root = None

def insert(nodes,z,root):
    x = root
    y = None
    while x != None:
        y = x
        if z < x:
            x = nodes[x][1]
        else:
            x = nodes[x][2]
    nodes[z][0] = y

    if y == None:
        root = z
    elif z < y:
        nodes[y][1] = z
    else:
        nodes[y][2] = z
    return root

for i in range(N):
    order = input().split()
    if order[0] == 'print':
        inParse(root)
        print()
        preParse(root)
        print()
        continue

    z = int(order[1])
    nodes[z] = [None,None,None]
    root = insert(nodes,z,root)

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

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

class BinarySearchTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        parent = self.root
        if parent is None:
            self.root = Node(data)
            return
        while parent:
            parent_old = parent
            parent = parent.left if data < parent.data else parent.right
        if data < parent_old.data:
            parent_old.left = Node(data)
        else:
            parent_old.right = Node(data)


def print_preorder(node):
    print(" {}".format(node.data))
    if node.left:
        print_preorder(node.left)
    if node.right:
        print_preorder(node.right)

def print_inorder(node):
    if node.left:
        print_inorder(node.left)
    print(" {}".format(node.data))
    if node.right:
        print_inorder(node.right)

if __name__ == "__main__":
    n = int(input())
    binary_search_tree = BinarySearchTree()
    for _ in range(n):
        operation, *num = input().split()
        if num:
            binary_search_tree.insert(int(num[0]))
        elif binary_search_tree.root is not None:
            print_inorder(binary_search_tree.root)
            print("\n")
            print_preorder(binary_search_tree.root)
            print("\n")

Solution (Python):


import sys
sys.setrecursionlimit(2**20)  

root = None

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_ls: list):
    
    if u == 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, u, in_ls):
    if u == 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, z):
    global root
    T[z] = Node()
    y = None 
    x = root 
    while (x is not None):
        y = x 
        if z < x:
            x = T[x].left 
        else:
            x = T[x].right 
    T[z].parent = y 
    if (y is None):
        root = z
    elif (z < y):
        T[y].left = z 
    else:
        T[y].right = z 


def find(T,  ROOT, k):
    x = ROOT 
    while T[x] is not None and x != k:
        if (k < x):
            T[x].left = x
        else:
            T[x].right = x
    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())
lst = [input().split() for i in range(N)]
T = {}
for i, c in enumerate(lst):
    if c[0] == 'insert':
        z = int(c[1])
        insert(T, z)
    elif c[0] == 'print':
        print_result(T)
    elif c[0] == 'find':
        is_find = find(T, root, z)
        if is_find is None:
            print('no')
        else:
            print('Yes')

Solution (Python):
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.order_list = []
    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.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
            
    def walk_preorder(self, node):
        if node == None:
            return None
        self.order_list.append(node.key)
        self.walk_preorder(node.left)
        self.walk_preorder(node.right)
    def walk_inorder(self, node):
        if node == None:
            return None
        self.walk_inorder(node.left)
        self.order_list.append(node.key)
        self.walk_inorder(node.right)
    def print_nodes(self):
        self.order_list = []
        self.walk_inorder(self.root)
        inorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(inorder_str))
        self.order_list = []
        self.walk_preorder(self.root)
        preorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(preorder_str))
        
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

n = int(input())
tree = BinarySearchTree()
for _ in range(n):
    command = input().split(' ')
    if len(command) == 1:
        tree.print_nodes()
    else:
        opecode, operand = command[0], int(command[1])
        node = Node(operand)
        tree.insert(node)

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):
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

root = None
def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z[2] < x[2]:
            x = x[0]
        else:
            x = x[1]
    z[3] = y

    if y is None:
        root = z
    elif z[2] < y[2]:
        y[0] = z
    else:
        y[1] = z

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0] is not None:
            dfs(nd[0])
        s1.append(v)
        if nd[1] is not None:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    else:
        insert([None, None, int(V[0]), None])
write("\n".join(ans))
write("\n")

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):
"""
二分探索木を構成する
"""
import copy

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

class Tree:
    def insert_root_node(self, new_id):
        global root_node 
        root_node = Node(new_id)

    def insert_node(self, root_id, new_id): 
        compare_node = root_node 
        new_node = Node(new_id) 
        while compare_node != None: 
            
            
            new_node.parent = compare_node 
            
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        
        
        if new_node.parent.node_id < new_id:
            new_node.parent.right = Node(new_id)
        else:
            new_node.parent.left = Node(new_id)

def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)


tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if root_node == None: 
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(root_id, new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    
class Tree():
    def __init__(self, root=None):
        self.root = root
    
    def insert(self, 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 print_inorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            work(node.left)
            print('', node.key, end='')
            work(node.right)

        work(self.root)
        print()
    
    def print_preorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            print('', node.key, end='')
            work(node.left)
            work(node.right)

        work(self.root)
        print()


import sys

n = int(input())
T = Tree()
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command[0] == 'i':   
        T.insert(Node(int(args[0])))
    else:   
        T.print_inorder_tree_walk()
        T.print_preorder_tree_walk()

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:
        y = x
        if key < x.key:
            x= x.left
        else:
            x = x.right

    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):
class Node():
    def __init__(self, parent=-1, left=-1, right=-1):
        self.parent = parent
        self.left = left
        self.right = right


class Tree(dict):
    def __init__(self, obj={}):
        if isinstance(obj, dict):
            super().__init__(obj)
        else:
            raise TypeError
        self.root = -1

    def insert_key(self, key):
        node = Node()
        parent = -1  
        target = self.root  
        while target != -1:
            parent = target
            if key < target:
                target = self[target].left
            else:
                target = self[target].right
        node.parent = parent
        self[key] = node
        if parent == -1:  
            self.root = key
        elif key < parent:
            self[parent].left = key
        else:
            self[parent].right = key

    def find(self, key):
        target = self.root
        while True:
            if target == key:
                return True
            if key < target:
                target = self[target].left
            else:
                target = self[target].right
            if target == -1:
                return False

    def __preorder(self, id):
        if id == -1:
            return []
        return [id] + self.__preorder(self[id].left) + self.__preorder(self[id].right)

    def __inorder(self, id):
        if id == -1:
            return []
        return self.__inorder(self[id].left) + [id] + self.__inorder(self[id].right)

    def __postorder(self, id):
        if id == -1:
            return []
        return self.__postorder(self[id].left) + self.__postorder(self[id].right) + [id]

    def __preorder_print(self, id):
        if id == -1:
            pass
        else:
            print(" {}".format(id), end="")
            self.__preorder_print(self[id].left)
            self.__preorder_print(self[id].right)

    def __inorder_print(self, id):
        if id == -1:
            pass
        else:
            self.__inorder_print(self[id].left)
            print(" {}".format(id), end="")
            self.__inorder_print(self[id].right)

    def __postorder_print(self, id):
        if id == -1:
            pass
        else:
            self.__postorder_print(self[id].left)
            self.__postorder_print(self[id].right)
            print(" {}".format(id), end="")

    def order_list(self, order_type):
        if order_type == 0:
            return self.__preorder(self.root)
        elif order_type == 1:
            return self.__inorder(self.root)
        else:
            return self.__postorder(self.root)

    def print(self):
        
        
        
        
        print(" {}".format(" ".join(map(str, self.order_list(1)))))
        print(" {}".format(" ".join(map(str, self.order_list(0)))))


def main():
    n = int(input())
    tree = Tree()
    for _ in range(n):
        operation = input()
        if operation[0] == "i":
            tree.insert_key(int(operation.split()[1]))
        elif operation[0] == "f":
            if tree.find(int(operation.split()[1])):
                print("yes")
            else:
                print("no")
        else:
            tree.print()


if __name__ == "__main__":
    main()

Solution (Python):
def insert(tree,node):
    parent=None
    child=root
    while child is not None:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    if node<parent:tree[parent][0]=node
    else:tree[parent][1]=node


def In_order(node):
    if node is None:return
    In_order(tree[node][0])
    print(" {}".format(node), end="")
    In_order(tree[node][1])


def Pre_order(node):
    if node is None:return
    print(" {}".format(node), end="")
    Pre_order(tree[node][0])
    Pre_order(tree[node][1])


n=int(input())
tree,root={},None
for i in range(n):
    order=input().split()
    if order[0]=="print":
        In_order(root);print()
        Pre_order(root);print()
    elif order[0]=="insert":
        num=int(order[1])
        if root is None:
            root=num
            tree[root]=[None,None]
        else:
            tree[num]=[None,None]
            insert(tree,num)