Problem:
Binary Search Tree II Write a program which performs the following operations to a binary search tree $T$ by adding the find operation to A: Binary Search Tree I.  insert $k$: Insert a node containing $k$ as key into $T$.  find $k$: Report whether $T$ has a node containing $k$.  print : Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.  Input In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$ or print are given. Output For each find $k$ operation, print " yes " if $T$ has a node containing $k$, " no " if not. In addition, 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 10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print Sample Output 1 yes
no
 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):
"""
二分探索木を構成する
"""
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 is not 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)

def find(search_id):
    tmp_node = root_node
    while tmp_node:
        if tmp_node.node_id == search_id:
            print('yes')
            return
        elif tmp_node.node_id < search_id:
            tmp_node = tmp_node.right
        else:
            tmp_node = tmp_node.left
    print('no')



tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if not root_node: 
        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()
    elif order[0][0] == 'f':
        find(int(order[1]))

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

    def find(self, key):
        x = self.root
        while x is not None:
            if key == x.key:
                return True
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return False

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])))
    elif command[0] == 'f': 
        if T.find(int(args[0])):
            print('yes')
        else:
            print('no')
    else:   
        T.print_inorder_tree_walk()
        T.print_preorder_tree_walk()

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):
        try:
            self[key]
            print("yes")
        except KeyError:
            print("no")

    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":
            tree.find(int(operation.split()[1]))
        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])


def find(x,key):
    while x is not None and key!=x:
        if key<x:x=tree[x][0]
        else:x=tree[x][1]
    return x


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]=="find":
        if find(root,int(order[1])) is not None:print("yes")
        else:print("no")
    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)

Solution (Python):



class NodeBintree:

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

    def insert_node (self, n):
        if (self.key is None) or (self.key > n.key):
            if self.left is None:
                self.left = n
            else:
                self.left.insert_node(n)
        else:
            if self.right is None:
                self.right = n
            else:
                self.right.insert_node(n)
    def find (self, key):
        if self.key is None:
            return self.left.find(key)
        elif self.key == key:
            return "yes"
        elif self.key > key:
            if self.left is None:
                return "no"
            else:
                return self.left.find(key)
        else:
            if self.right is None:
                return "no"
            else:
                return self.right.find(key)

    def traverse_inorder (self):
        ret = ""

        if self.left is not None:
            ret += self.left.traverse_inorder()

        if self.key is not None:
            ret += " {0}".format(self.key)

        if self.right is not None:
            ret += self.right.traverse_inorder()

        return ret

    def traverse_preorder (self):
        ret = ""

        if self.key is not None:
            ret += " {0}".format(self.key)

        if self.left is not None:
            ret += self.left.traverse_preorder()

        if self.right is not None:
            ret += self.right.traverse_preorder()

        return ret

def proc_inputs ():
    num_inputs = int(input())
    inputs = [proc_command(input().split()) for i in range(num_inputs)]
    return inputs

def proc_command (l):
    if len(l) > 1:
        arg = l[1]
    else:
        arg = None
    return {"command": l[0], "arg": arg}

def execute_command (tree, command):
    if command["command"] == "insert":
        tree.insert_node(NodeBintree(int(command["arg"])))

    elif command["command"] == "find":
        print(tree.find(int(command["arg"])))

    elif command["command"] == "print":
        print(tree.traverse_inorder() )
        print(tree.traverse_preorder() )

    return


def main ():
    inputs = proc_inputs()
    tree = NodeBintree(None)
    for command in inputs:
        execute_command(tree, command)
    exit(0)


if __name__ == "__main__":
    main()

Solution (Python):


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

def insert(root, z):
    y = None
    x = None
    if root != 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 find(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x

def printInOrder(z):
    if z == None:
        return
    if z.left != None:
        printInOrder(z.left)
    inorder.append(str(z.key))
    
    if z.right != None:
        printInOrder(z.right)
        
def printPreOrder(z):
    if z == None:
        return
    
    preorder.append(str(z.key))
    if z.left != None:
        printPreOrder(z.left)
    if z.right != None:
        printPreOrder(z.right)

root = None


n = int(input())
for i in range(n):
    command = input()
    if command[0] == "i":
        com,num = command.split()
        z = Node(int(num))
        insert(root, z)
        if root == None:
            root = z
    elif command[0] == "f":
        com,num = command.split()
        z = Node(int(num))
        x = find(root, int(z.key))
        if x != None:
            print("yes")
        else:
            print("no")

    else:
        inorder = []
        printInOrder(root)
        print(" ", end = "")
        print(' '.join(inorder))
        preorder = []
        printPreOrder(root)
        print(" ", end = "")
        print(' '.join(preorder))

Solution (Python):
class BinarySearchTree:
    def __init__(self):
        self.lcs = {}
        self.rcs = {}
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = key
            self.lcs[key] = None
            self.rcs[key] = None
            return
        parent = self.root
        while True:
            if key < parent:
                if self.lcs[parent] is None:
                    self.lcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.lcs[parent]
            else:
                if self.rcs[parent] is None:
                    self.rcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.rcs[parent]

    def _find(self, key, cur):
        if key == cur:
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._find(key, self.lcs[cur])
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._find(key, self.rcs[cur])

    def find(self, key):
        return self._find(key, self.root)

    def _print(self, cur):
        self.preorder.append(cur)
        if self.lcs[cur]:
            self._print(self.lcs[cur])
        self.inorder.append(cur)
        if self.rcs[cur]:
            self._print(self.rcs[cur])

    def print(self):
        self.preorder = []
        self.inorder = []
        self._print(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))


T = BinarySearchTree()
N = int(input())
for _ in range(N):
    s = input().split()
    if s[0] == 'insert':
        T.insert(int(s[1]))
    elif s[0] == 'find':
        print('yes' if T.find(int(s[1])) else 'no')
    else:
        T.print()

Solution (Python):

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

class Tree:
    def __init__(self):
        self.root = None
        self.list = []
    
    def insert(self, node_tobe_added):
            y = None 
            x = self.root
            while x != None:
                
                y = x
                if node_tobe_added.key < x.key:
                    x = x.left
                else:
                    x = x.right
            
            node_tobe_added.parent = y 
            
            
            if y == None:
                self.root = node_tobe_added
            elif node_tobe_added.key < y.key:
                
                y.left = node_tobe_added
            else:
                
                y.right = node_tobe_added
                
    def find(self, key):
        x = self.root
        while x != None and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x
                
    def preParse(self, node):
        if node == None:
            return
        self.list.append(node.key)
        self.preParse(node.left)
        self.preParse(node.right)
    
    def inParse(self, node):
        if node == None:
            return
        self.inParse(node.left)
        self.list.append(node.key)
        self.inParse(node.right)

T = Tree()

N = int(input())
for i in range(N):
        order, *key = input().split() 
        if order == "print":
            T.list = []
            T.inParse(T.root)
            print(" " + " ".join(map(str, T.list)))
            T.list = []
            T.preParse(T.root)
            print(" " + " ".join(map(str, T.list)))
        elif order == "insert":
            T.insert(Node(int(key[0]))) 
        else:
            if T.find(int(key[0])):
                print("yes")
            else:
                print("no")

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

class BinaryTree():
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            parentnode = curnode = self.root
            while curnode != None:
                parentnode = curnode
                if curnode.value > value:
                    curnode = curnode.left
                else:
                    curnode = curnode.right
            if value > parentnode.value:
                parentnode.right = Node(value)
            else:
                parentnode.left = Node(value)

    def find(self, value):
        curnode = self.root
        while curnode != None:
            if curnode.value == value:
                return True
            elif curnode.value < value:
                curnode = curnode.right
            else:
                curnode = curnode.left
        return False

    def preorder(self, root):
        if root == None:
            pass
        else:
            print(' %d' % root.value, end='')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root == None:
            pass
        else:
            self.inorder(root.left)
            print(' %d' % root.value, end='')
            self.inorder(root.right)

if __name__ == '__main__':
    n = int(input())
    binarytree = BinaryTree()
    for _ in range(n):
        common = input()
        if common[0] == 'i':
            binarytree.insert(int(common[7:]))
        elif common[0] == 'f':
            if binarytree.find(int(common[5:])):
                print('yes')
            else:
                print('no')
        else:
            binarytree.inorder(binarytree.root)
            print()
            binarytree.preorder(binarytree.root)
            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 find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

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:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Solution (Python):

class Node:
    key = None
    parent = None
    left = None
    right = None

    def __init__(self, key):
        self.key = key


def insert(key):
    global T
    global root

    new_node = Node(key)
    T.append(new_node)

    if root is None:
        root = new_node

    else:
        y = None  
        x = root  

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

        new_node.parent = y
        if new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node


def find(key):
    global T
    global root

    x = root

    while x is not None and key != x.key:
        

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


def in_order(node, order):
    if node is None:
        return

    in_order(node.left, order)
    order.append(node.key)
    in_order(node.right, order)


def pre_order(node, order):
    if node is None:
        return

    order.append(node.key)
    pre_order(node.left, order)
    pre_order(node.right, order)


m = int(input())
T = []
root = None

for i in range(m):
    order = input()

    if order.startswith('print'):
        output = []
        in_order(root, output)
        
        print(' ' + ' '.join(map(str, output)))

        output = []
        pre_order(root, output)
        
        print(' ' + ' '.join(map(str, output)))

    elif order.startswith('find'):
        order, value = order.split()
        value = int(value)
        _ = find(value)
        if _ is None:
            print('no')
        else:
            print('yes')

    else:
        order, value = order.split()
        value = int(value)
        insert(value)

Solution (Python):
class Node:
    def __init__(self, v=None, l=None, r=None):
        self.value = v
        self.left = l
        self.right = r

class Tree:
    def __init__(self):
        self.root = Node()
    
    def insert(self, v):
        if self.root.value is None:
            self.root.value = v
            return
        node = self.root
        while node is not None:
            if v < node.value:
                if node.left is None:
                    node.left = Node(v)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(v)
                    return
                node = node.right

    def find(self, v):
        node = self.root
        while node != None:
            if v == node.value:
                print "yes"
                return
            elif v < node.value:
                node = node.left
            else:
                node = node.right
        print "no"
        return

    def print_tree(self, order):
        ans = []
        def rec(node):
            if node is None:
                return
            if order == "pre":
                ans.append(str(node.value))
            if node.left is not None:
                rec(node.left)
            if order == "in":
                ans.append(str(node.value))
            if node.right is not None:
                rec(node.right)
        rec(self.root)
        print " " + " ".join(ans)

tree = Tree()
N = int(raw_input())
for _ in range(N):
    d = raw_input().split()
    cmd = d[0]
    if cmd == "insert":
        tree.insert(int(d[1]))
    elif cmd == "find":
        tree.find(int(d[1]))
    elif cmd == "print":
        tree.print_tree("in")
        tree.print_tree("pre")

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 find(k):
    x = root
    while x is not None:
        if x[2] == k:
            return 1
        if k < x[2]:
            x = x[0]
        else:
            x = x[1]
    return 0

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())
    elif cmd == "find":
        ans.append("yes" if find(int(V[0])) else "no")
    else:
        insert([None, None, int(V[0]), None])
write("\n".join(ans))
write("\n")

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

def insert(z):
    global root
    if root==None:
        root=Node(z)
    else:
        x=root
        while True:
            if z<x.key:
                if x.left:
                    x=x.left
                else:
                    x.left=Node(z)
                    break
            else:
                if x.right:
                    x=x.right
                else:
                    x.right=Node(z)
                    break
def inorder(z):
    if z==None:
        return []
    else:
        return inorder(z.left)+[z.key]+inorder(z.right)
def preorder(z):
    if z==None:
        return []
    else:
        return [z.key]+preorder(z.left)+preorder(z.right)
def find(z):
    global root
    x=root
    r="no"
    while x:
        if z==x.key:
            r="yes"
            break
        elif z<x.key:
            x=x.left
        else:
            x=x.right
    return r
root=None
n=int(input())
for _ in range(n):
    p=input()
    if p[0]=="i":
        insert(int(p[7:]))
    elif p[0]=="f":
        print(find(int(p[5:])))
    else:
        print("",*inorder(root))
        print("",*preorder(root))

Solution (Python):
import sys
input = sys.stdin.readline
btree = []
root = None


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


def showInorder(node):
    if node.left is not None:
        showInorder(node.left)
    print(" {0}".format(str(node.key)), end="")
    if node.right is not None:
        showInorder(node.right)


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


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


def find(key):
    global root
    x = root
    while x is not None:
        if x.key == key:
            print('yes')
            return
        elif x.key > key:
            x = x.left
        else:
            x = x.right
    print('no')



def showtree(root):
    showInorder(root)
    print()
    showPreorder(root)
    print()


def main():
    m = int(input())
    global root
    for i in range(m):

        operation = input().split()

        

        if operation[0] == 'insert':
            
            insert(int(operation[1]))
        elif operation[0] == 'find':
            find(int(operation[1]))
        else:
            
            
            showtree(root)


if __name__ == '__main__':
    main()

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

def preParse(u):
    if u == -1:
        return
    print(" " + str(u), end = '')
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1:
        return
    inParse(T[u].l)
    print(" " + str(u), end = '')
    inParse(T[u].r)

def postParse(u):
    if u == -1:
        return
    postParse(T[u].l)
    postParse(T[u].r)
    print(" " + str(u), end = '')

root = -1
def insert(T, z):
    global root
    parent = -1
    u = root
    while u != -1:
        parent = u
        if z < u:
            u = T[u].l
        else:
            u = T[u].r
    T[z].p = parent
    if parent == -1:
        root = z
    elif z < parent:
        T[parent].l = z
    else:
        T[parent].r = z

def find(T, k):
    u = root
    while u != -1 and k != u:
        if k < u:
            u = T[u].l
        else:
            u = T[u].r
    return "no" if u == -1 else "yes"

n = int(input())
cmdList = [input() for _ in range(n)]
T = {int(cmd[7:]): node() for cmd in cmdList if cmd[0] == "i"}

for cmd in cmdList:
    if cmd[0] == "p":
        inParse(root)
        print("")
        preParse(root)
        print("")
    elif cmd[0] == "f":
        print(find(T, int(cmd[5:])))
    else:
        insert(T, int(cmd[7:]))