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):
from sys import stdin

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

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

    def insert(self, v):
        cur = self.root
        cur_p = None
        while cur != None:
            cur_p = cur
            if v < cur.value:
                cur = cur.left
            elif v > cur.value:
                cur = cur.right

        n = Node(v, cur_p)
        if cur_p == None:
            self.root = n
        elif v < cur_p.value:
            cur_p.left = n
        else:
            cur_p.right = n

    def preorder(self):

        def rec_preorder(t=self.root):
            if t != None:
                print(" ", t.value, sep="", end="")
                rec_preorder(t.left)
                rec_preorder(t.right)

        rec_preorder()
        print()

    def inorder(self):

        def rec_inorder(t=self.root):
            if t != None:
                rec_inorder(t.left)
                print(" ", t.value, sep="", end="")
                rec_inorder(t.right)

        rec_inorder()
        print()

    def find(self, x):

        def rec_find(t=self.root):
            if t == None:
                return False
            elif x > t.value:
                return rec_find(t.right)
            elif x < t.value:
                return rec_find(t.left)
            else:
                return True

        return rec_find()

m = int(stdin.readline().rstrip())
t = BST()
for _ in range(m):
    q = stdin.readline().rstrip().split()
    if q[0] == "insert":
        t.insert(int(q[1]))
    elif q[0] == "find":
        if t.find(int(q[1])):
            print("yes")
        else:
            print("no")
    elif q[0] == "print":
        t.inorder()
        t.preorder()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import defaultdict

class Node:
    def __init__(self, key):
        self.key = key
        self.par = -1
        self.left = -1
        self.right = -1

root = None
nodes = defaultdict(lambda: None)

def insert(z):
    global root
    
    y = None
    x = root
    
    while x is not None:
        y = x
        if z.key < x.key:
            
            x = nodes[x.left]
        else:
            
            x = nodes[x.right]
    if y is None:
        z.par = -1
    else:
        z.par = y.key
    
    if y is None:
        
        root = z
    elif z.key < y.key:
        
        y.left = z.key
    else:
        
        y.right = z.key

def find(key):
    if nodes[key]:
        print('yes')
    else:
        print('no')

def tree_walk(node):
    preo.append(node.key)
    if node.left != -1:
        tree_walk(nodes[node.left])
    ino.append(node.key)
    if node.right != -1:
        tree_walk(nodes[node.right])
    return

N = INT()

for _ in range(N):
    instr = input()
    if instr == 'print':
        preo = []
        ino = []
        tree_walk(root)
        print('', *ino)
        print('', *preo)
    elif instr.startswith('insert'):
        _, key = instr.split()
        key = int(key)
        node = Node(key)
        nodes[key] = node
        insert(node)
    else:
        _, key = instr.split()
        find(int(key))

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 STsearch(h, k):
    while h.key != -1:
        if k < h.key:
            h = h.left
        elif h.key < k:
            h = h.right
        else:
            print("yes")
            return
    print("no")

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)
    elif temp[0] == "print":
        A = []
        B = []
        inorder(head, head, B)
        preorder(head, head, A)
    else:
        STsearch(head, int(temp[1]))

Solution (Python):

class Node:

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


def input_line() -> (str, int):
    line = input().split()
    if line[0] == 'insert':
        return line[0], int(line[1])
    elif line[0] == 'find':
        return line[0], int(line[1])
    else:
        return line[0], None


def preorder(tree: Node) -> None:
    """先行順巡回。"""
    print(f' {tree.key}', end='')
    if tree.left is not None:
        preorder(tree.left)
    if tree.right is not None:
        preorder(tree.right)


def inorder(tree: Node) -> None:
    """中間順巡回。"""
    if tree.left is not None:
        inorder(tree.left)
    print(f' {tree.key}', end='')
    if tree.right is not None:
        inorder(tree.right)


def insert(new_node: Node) -> None:
    """二分探索木に挿入する。"""

    
    global root

    
    parent = None

    
    tmp = root

    
    while tmp is not None:
        parent = tmp
        if new_node.key < tmp.key:
            tmp = tmp.left
        else:
            tmp = tmp.right

    
    new_node.parent = parent

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


def find(key)-> bool:

    global root

    
    tmp = root

    
    while tmp is not None:
        if key == tmp.key:
            return True
        elif key < tmp.key:
            tmp = tmp.left
        else:
            tmp = tmp.right

    return False


root = None  
N = int(input())
for _i in range(N):
    order, val = input_line()
    if order == 'insert':
        node = Node(val)
        insert(node)
    elif order == 'print':
        inorder(root)
        print()
        preorder(root)
        print()
    elif order == 'find':
        if find(val):
            print('yes')
        else:
            print('no')

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

    def __repr__(self):
        return str(self.key)

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

def find(T, k):
    y = None
    x = T 
    while x != None:
        y = x
        if k == x.key:
            print('yes')
            return
        if k < x.key:
            x = x.left
        else:
            x = x.right
    print('no')
    


def printPreorder(x):
    if x == None:
        return
    printPreorder(x.left)
    print(end=' ')
    print(x,end='')
    printPreorder(x.right)

def printMidorder(x):
    if x == None:
        return
    print(end=' ')
    print(x,end='')
    printMidorder(x.left)
    printMidorder(x.right)

def printal(x):
    printPreorder(x)
    print()
    printMidorder(x)
    print()


N = int(input())
Q = input().split()
T = Node(int(Q[1]),None,None,None)
for i in range(N-1):
    Q = input().split()
    if Q[0] == "print":
        printal(T)
        continue
    elif Q[0] == "find":
        find(T,int(Q[1]))
        continue
    insert(T,Node(int(Q[1]),None,None,None))

Solution (Python):
def insert(z):
    global root
    y = NIL
    x = root
    
    while x != NIL:
        y = x
        if z < x:
            x = TL[x]
        else:
            x = TR[x]
    TP[z] = y

    if y == NIL:
        root = z
    elif z < y:
        TL[y] = z
    else:
        TR[y] = z


def inorder(u):
    if u == NIL:
        return
    inorder(TL[u])
    print(' ', end='')
    print(u, end='')
    inorder(TR[u])


def preorder(v):
    if v == NIL:
        return
    print(' ', end='')
    print(v, end='')
    preorder(TL[v])
    preorder(TR[v])


TR = {}
TL = {}
TP = {}
NIL = None
root = NIL
m = int(input())
data = [input().split() for _ in range(m)]

for i in data:
    if i[0][0] == 'i':
        TR[int(i[1])] = TL[int(i[1])] = NIL
        insert(int(i[1]))
    elif i[0][0] == 'f':
        if int(i[1]) in TR:
            print('yes')
        else:
            print('no')
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):
import sys


class Node:
    __slots__ = ['key', 'parent', 'left', 'right']

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


def insert(root, z):
    if root is None:
        return z

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

    return root


def find(node, key):
    if not node:
        return False

    if key < node.key:
        return find(node.left, key)
    if key > node.key:
        return find(node.right, key)

    return True  


def inorder(node):
    if not node:
        return
    yield from inorder(node.left)
    yield node.key
    yield from inorder(node.right)


def preorder(node):
    if not node:
        return
    yield node.key
    yield from preorder(node.left)
    yield from preorder(node.right)


def print_tree(root):
    print(''.join(' ' + str(key) for key in inorder(root)))
    print(''.join(' ' + str(key) for key in preorder(root)))


root = None

n = int(sys.stdin.readline())
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command == 'insert':
        root = insert(root, Node(int(args[0])))
    elif command == 'find':
        print('yes' if find(root, int(args[0])) else 'no')
    else:
        print_tree(root)

Solution (Python):




import sys
input = sys.stdin.readline
import cProfile

class node:
    def __init__(self,nodeid):
        self.parent = None
        self.c_left = None
        self.c_right = None
        self.nodeid = nodeid

    def setChild(self,n,cn=None):
        if (cn == None):
            cn = self
        if ( cn.nodeid < n):
            if (cn.c_right == None):
                cn.c_right = node(n) 
                cn.c_right.parent =  cn 
            else:
                self.setChild(n,cn.c_right)
        else:
            if (cn.c_left == None):
                cn.c_left = node(n) 
                cn.c_left.parent =  cn 
            else:
                self.setChild(n,cn.c_left)

    def getPreorder(self,r1=[]):
        r1.append(self.nodeid)
        if (self.c_left != None):
            r1 = self.c_left.getPreorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPreorder(r1)
        return r1       
    def getInorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getInorder(r1)
        r1.append(self.nodeid)
        if (self.c_right != None):
            r1 = self.c_right.getInorder(r1)
        return r1       
    def getPostorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getPostorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPostorder(r1)
        r1.append(self.nodeid)
        return r1       

    def find(self,n):
        if self.nodeid == n:
            return True
        if self.nodeid > n:
            if (self.c_left == None ):
                return False
            return self.c_left.find(n)
        else:
            if  (self.c_right == None):
                return False
            return self.c_right.find(n)
    
    def getRoot(self):
        if (self.parent == None):
            return self
        return self.parent.getRoot()

def main():
    n = int(input())
    root = None
    for i in range(n):
        l = list(map(str,input().split()))
        if (l[0] == "print" and root != None):
            print("",*root.getInorder([]))
            print("",*root.getPreorder([]))
        elif (l[0] == "insert"):
            d = int(l[1])
            if ( root == None):
                root = node(d)
            else:
                root.setChild(d)
        elif (l[0] == "find"):
            d = int(l[1])
            r = root.find(d)
            if (r == True):
                print ("yes")
            else:
                print ("no")

if __name__ == '__main__':
    main()

Solution (Python):
import sys
class Node:
    parent = -1
    left = -1
    right = -1

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

    def __repr__(self):
        return "k:{},p:{},l:{},r:{}".format(self.key, self.parent, self.left, self.right)

root_node_no = -1

def insert(nodes :dict, in_node :Node):
    global root_node_no

    cur_node_no = root_node_no
    parent_node_no = -1
    while cur_node_no != -1:
        parent_node_no = cur_node_no
        if in_node.key < cur_node_no:
            cur_node_no = nodes[cur_node_no].left
        else:
            cur_node_no = nodes[cur_node_no].right

    in_node.parent = parent_node_no

    if root_node_no == -1:
        root_node_no = in_node.key
    elif in_node.key < parent_node_no:
        nodes[parent_node_no].left = in_node.key
    else:
        nodes[parent_node_no].right = in_node.key

    nodes[in_node.key] = in_node

def inorder_tree_walk(nodes, node_no ,inorder):
    if node_no == -1:
        return
    inorder_tree_walk(nodes, nodes[node_no].left, inorder)
    inorder.append(node_no)
    inorder_tree_walk(nodes, nodes[node_no].right, inorder)

def preorder_tree_walk(nodes, node_no, preorder):
    if node_no == -1:
        return
    preorder.append(node_no)
    preorder_tree_walk(nodes, nodes[node_no].left, preorder)
    preorder_tree_walk(nodes, nodes[node_no].right, preorder)


def find(nodes, tgt_node_no):
    cur_node_no = root_node_no
    while cur_node_no != -1:
        cur_node = nodes[cur_node_no]
        if cur_node.key == tgt_node_no:
            return True
        elif tgt_node_no < cur_node.key:
            cur_node_no = cur_node.left
        else:
            cur_node_no = cur_node.right

    return False


def main():
    num_com = int(input())
    commands = sys.stdin.readlines()
    nodes = {}
    for i in range(num_com):
        if commands[i][0] == 'i':
            insert(nodes, Node(int(commands[i][7:])))
        elif commands[i][0] == 'p':
            
            inorder = []
            inorder_tree_walk(nodes, root_node_no, inorder)
            print(" " + " ".join(map(str, inorder)))
            
            preorder = []
            preorder_tree_walk(nodes, root_node_no, preorder)
            print(" " + " ".join(map(str, preorder)))
        elif commands[i][0] == 'f':
            if find(nodes, int(commands[i][5:])):
                print('yes')
            else:
                print('no')


main()

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


def insert(root,node):
    if(root.key <= node.key):
        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 find(root,key):
    if(root.key==key):
        return 1

    elif(root.key < key):
        if(root.right is not None):
            return find(root.right,key)
        else:
            return 0

    else:
        if(root.left is not None):
            return find(root.left,key)
        else:
            return 0



    

def Preorder(root,order):
    order.append(root.key)
    if(root.left is not None):
        Preorder(root.left,order)
    
    if(root.right is not None):
        Preorder(root.right,order)




def Inorder(root,order):
    if(root.left is not None):
        Inorder(root.left,order)
    
    order.append(root.key)

    if(root.right is not None):
        Inorder(root.right,order)




n=int(input())

root=None

for loop in range(n):
    ope=input().split()

    if(ope[0]=="insert"):
        tmp_node=Node(int(ope[1]))
        try:
            insert(root,tmp_node)
        except:
            root=tmp_node
    
    elif(ope[0]=="find"):
        try:
            if(find(root,int(ope[1]))):
                print("yes")

            else:
                print("no")
        except:
            print("no")

    else:
        in_order=[]
        p_order=[]
        
        Inorder(root,in_order)
        Preorder(root,p_order)

        for x in in_order:
            print(f" {x}",end="")
        print()
        for x in p_order:
            print(f" {x}",end="")
        print()

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, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        

class Tree:
    def __init__(self):
        self.root_node = None
        
    def insert(self, z):
        y = None 
        x = self.root_node 
        
        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_node = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    
    def find(self, k):
        x = self.root_node
        while (x is not None) and (x.key != k):
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x
        
    
    def print_preorder(self, node):
        print(f" {node.key}", end="")
        if node.left is not None:
            self.print_preorder(node.left)
        if node.right is not None:
            self.print_preorder(node.right)

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

    def print_nodes(self):
        if self.root_node is None:
            pass
        else:
            self.print_inorder(self.root_node)
            print("")
            self.print_preorder(self.root_node)
            print("")

        
tree = Tree()

m = int(input())

for _ in range(m):
    command = input().split()
    if command[0] == 'print':
        tree.print_nodes()
    elif command[0] == 'find':
        node = tree.find(int(command[1]))
        print("no") if (node is None) else print("yes")
    else:
        key = int(command[1])
        new_node = Node(key)
        tree.insert(new_node)

Solution (Python):
from sys import stdin

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

class BinarySearchTree(object):
    def __init__(self):
        self.tree = {}
        self.root = None

    def insert(self, z):
        if not self.tree:
            self.tree[z] = Node(parent=-1)
            self.root = z
        else:
            x = self.root
            while x != None:
                y = x
                if z < x:
                    x = self.tree[x].left
                else:
                    x = self.tree[x].right

            self.tree[z] = Node(parent=y)
            if z < y:
                self.tree[y].left = z
            else:
                self.tree[y].right = z

    def print_nodes(self):
        A = [] 
        B = [] 
        def walk_tree(u):
            if u == None:
                return
            r = self.tree[u].right
            l = self.tree[u].left
            A.append(u)
            walk_tree(l)
            B.append(u)
            walk_tree(r)

        walk_tree(self.root)
        print(" ", end="")
        print(*B, sep=" ")
        print(" ", end="")
        print(*A, sep=" ")

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

    def find_print(self, k):
        if self.find(k) != None:
            print("yes")
        else:
            print("no")

def read_and_print_BSTree(bst, n):
    for _ in range(n):
        cmd = stdin.readline().strip().split()
        if cmd[0] == 'insert':
            bst.insert(int(cmd[1]))
        elif cmd[0] == 'print':
            bst.print_nodes()
        elif cmd[0] == 'find':
            bst.find_print(int(cmd[1]))

n = int(input())
bst = BinarySearchTree()
read_and_print_BSTree(bst, n)

Solution (Python):



from sys import stdin


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

    def insert(self, z):

        y = None
        x = self.root

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

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

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

    def print_inorder(self):
        def rec(node):
            if not node:
                return
            else:
                rec(node.left)
                print("", node.key, end="")
                rec(node.right)

        rec(self.root)
        print()

    def print_preorder(self):

        def rec(node):
            if not node:
                return
            else:
                print("", node.key, end="")
                rec(node.left)
                rec(node.right)

        rec(self.root)
        print()


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


def main():
    _ = int(stdin.readline())
    T = Tree()

    for line in stdin:
        cmd, *args = line.split()
        if cmd == "insert":
            T.insert(Node(int(args[0])))
        if cmd == "find":
            print("yes" if T.find(int(args[0])) else "no")
        elif cmd == "print":
            T.print_inorder()
            T.print_preorder()


main()

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 find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    if result is None:
        return False
    else:
        return True

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

def in_order(node):
    if node is None:
        return ''
    return in_order(node.left) + f' {node.key}' + in_order(node.right)
def pre_order(node):
    if node is None:
        return ''
    return f' {node.key}' + pre_order(node.left) + pre_order(node.right)
input()
for e in sys.stdin:
    if e[0] == 'i':
        insert(int(e[7:]))
    elif e[0] == 'f':
        print('yes' if find(int(e[5:])) else 'no')
    else:
        print(in_order(root))
        print(pre_order(root))

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):
        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 find(self, key):
        node = self.root
        while node is not None and key != node.key:
            if key < node.key:
                node = node.left
            else:
                node = node.right
        
        return node

    def parse_inorder(self, node):
        if node is None:
            return 
        self.parse_inorder(node.left)
        self.list.append(node.key)
        self.parse_inorder(node.right)

    def parse_preorder(self, node):
        if node is None:
            return
        self.list.append(node.key)
        self.parse_preorder(node.left)
        self.parse_preorder(node.right)

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

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
        
    def insert(self, z):
        if z.key < self.key:
            if self.left:
                self.left.insert(z)
            else:
                self.left = z
                z.parent = self
        else:
            if self.right:
                self.right.insert(z)
            else:
                self.right = z
                z.parent = self

    def find(self, key):
        if self.key == key:
            return True
        elif not(self.left or self.right):
            return False
        else:
            if key < self.key:
                return self.left.find(key)
            else:
                return self.right.find(key)
    def preo(self):
        tmp = ""
        tmp += " " + str(self.key)
        if self.left:
            tmp += self.left.preo()
        if self.right:
            tmp += self.right.preo()
        return tmp
    
    def ino(self):
        tmp = ""
        if self.left:
            tmp += self.left.ino()
        tmp += " " + str(self.key)
        if self.right:
            tmp += self.right.ino()
        return tmp
    
m = int(input())
root = None
for i in range(m):
    com = input().split()
    if com[0] == "insert":
        node = Node(int(com[1]))
        try:
            root.insert(node)
        except AttributeError :
            root = node
    elif com[0] == "find":
        try:
            if root.find(int(com[1])):
                print("yes")
            else:
                print("no")
        except AttributeError:
            print("no")
    else:
        try:
            print(root.ino())
            print(root.preo())
        except AttributeError:
            print("None")