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):
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 binarysearchtree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None
 
    def insert(self, z):
        z = node(z)
        y = None
        x = self.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:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
 
    def inorder(self):
        def inparse(u):
            if u == None:
                return
            inparse(u.left)
            print(" " + str(u.key), end="")
            inparse(u.right)
        inparse(self.root)
        print("")

    def outorder(self):
        def outparse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            outparse(u.left)
            outparse(u.right)
        outparse(self.root)
        print("")
 
    def print(self):
        self.inorder()
        self.outorder()
 
    def find(self, k):
        x = self.root
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x
 
n = int(input())
clist = [input().split(" ") for i in range(n)]
tree = binarysearchtree()

for c in clist:
    if c[0] == "insert":
        tree.insert(int(c[1]))
    elif c[0] == "find":
        f = tree.find(int(c[1]))
        if f is None:
            print("no")
        else:
            print("yes")
    else:
        tree.print()

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


def Pre(t, l):
    l.append(str(t.n))
    if t.left != None:
        Pre(t.left, l)
    if t.right != None:
        Pre(t.right, l)


def In(t, l):
    if t.left != None:
        In(t.left, l)
    l.append(str(t.n))
    if t.right != None:
        In(t.right, l)


def insert(t, z):
    y = None
    x = t
    while x != None:
        y = x
        if z.n < x.n:
            x = x.left
        else:
            x = x.right
    if y == None:
        return z
    else:
        if z.n < y.n:
            y.left = z
        else:
            y.right = z
        return t


def Find(t, p):
    if t.n == p:
        return True
    elif t.left != None and t.n > p:
        a = Find(t.left, p)
    elif t.right != None and t.n < p:
        a = Find(t.right, p)
    else:
        return False
    return a


def BST2(A, n):
    tree = None
    for i in range(n):
        if A[i] == "print":
            PreAns = []
            InAns = []
            Pre(tree, PreAns)
            In(tree, InAns)
            print(" "+" ".join(InAns))
            print(" "+" ".join(PreAns))
        else:
            if A[i].split(" ")[0] == "find":
                c = "no"
                point = int(A[i].split(" ")[1])
                if Find(tree, point) == True:
                    print("yes")
                else:
                    print("no")

            else:
                z = Node(int(A[i].split(" ")[1]))
                tree = insert(tree, z)


if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        A.append(input())
    BST2(A, n)

Solution (Python):

"""
Created on Thu Jul 19 22:51:44 2018

@author: maezawa
"""

class node():
    def __init__(self, key, parent=None, right=None, left=None):
        self.key = key
        self.parent = parent
        self.right = right
        self.left = left
        
def insert(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 find(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x
        
def inorder(u):
    if u == None:
        return
    inorder(u.left)
    print(' {}'.format(u.key), end = '')
    inorder(u.right)
    
def preorder(u):
    if u == None:
        return
    print(' {}'.format(u.key), end = '')
    preorder(u.left)
    preorder(u.right)
    
root = None

n = int(input())
for i in range(n):
    q = list(input().split())
    if q[0] == 'insert':
        z = node(int(q[1]))
        insert(z)
    elif q[0] == 'find':
        if find(root, int(q[1])):
            print('yes')
        else:
            print('no')
    elif q[0] == 'print':
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):


class MakeTree():
    def __init__(self, key, p=None, l=None, r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r
 
def Insert(root,value):
    y = None
    x = root
    z = MakeTree(value)

    while x != None:
        y = x
        if x.key > z.key:
            x = x.l
        else:
            x = x.r
    z.p = y

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


def Find(u, target):
    y = None
    x = u
    while x != None and target != x.key:
        y = x
        if x.key > target:
            x = x.l
        else:
            x = x.r
    if x == None:
        print("no")
    else:
        print("yes")
            
    

def inParse(u):
    if u == None:
        return
    inParse(u.l)
    global inParseList
    inParseList.append(u.key)
    inParse(u.r)

def preParse(u):
    if u == None:
        return
    global preParseList
    preParseList.append(u.key)
    preParse(u.l)
    preParse(u.r)


root = None       
n = int(input())
inParseList = []
preParseList = []
for i in range(n):
    order = list(input().split())
    if order[0] == "insert":
        root = Insert(root, int(order[1]))
        
    elif order[0] == "print":
        inParse(root)
        preParse(root)
        print(" " + " ".join([str(i) for i in inParseList]))
        print(" " + " ".join([str(i) for i in preParseList]))
        preParseList = []
        inParseList = []
        
    elif order[0] == "find":
        Find(root, int(order[1]))

Solution (Python):
from io import StringIO

class BinaryTree:

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


    def __init__(self):
        self.root = None
        self.output = StringIO()

    def insert(self, key):
        if self.root is None:
            self.root = self.Node(key)
        else:
            root = self.root
            temp = None
            while True:
                temp = root
                if key > root.key:
                    root = root.right
                    if root is None:
                        temp.right = self.Node(key)
                        break
                else:
                    root = root.left
                    if root is None:
                        temp.left = self.Node(key)
                        break

    def ini_print_inorder(self):
        self.output = StringIO()
        self.print_inorder(self.root)
        return self.output.getvalue()

    def ini_print_preorder(self):
        self.output = StringIO()
        self.print_preorder(self.root)
        return self.output.getvalue()

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

    def print_preorder(self, node):
        if node is not None:
            print(node.key, end = " ", file = self.output)
            self.print_preorder(node.left)
            self.print_preorder(node.right)

    def test_insert(self, keys):
        for k in keys:
            self.insert(k)

    def ini_find(self, key):
        print(self.find(key))

    def find(self, key):
        root = self.root
        while root is not None:
            if key == root.key:
                return "yes"
            elif key < root.key:
                root = root.left
            else:
                root = root.right
        return "no"


length = int(input())
b = BinaryTree()
for _ in range(length):
    comm = input()
    if comm[0] == "i":
        com, num = comm.split(" ")
        b.insert(int(num))
    elif comm[0] == "p":
        print(" ", end = "")
        print((b.ini_print_inorder())[:-1])
        print(" ", end = "")
        print(b.ini_print_preorder()[:-1])
    else:
        com, num = comm.split(" ")
        b.ini_find(int(num))

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

class BST:
  root = None
  def insert(self, key):
    x = self.root
    y = None
    z = Node(key)
    while x != None:
      y = x
      if(z.key < y.key):
        x = x.left
      elif(y.key < z.key):
        x = x.right
    
    if y is None:
      
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def preorder(self, par):
    if par is not None:
      print(" {}".format(par.key), end="")
      self.preorder(par.left)
      self.preorder(par.right)
  
  def inorder(self, par):
    if par is not None:
      self.inorder(par.left)
      print(" {}".format(par.key), end="")
      self.inorder(par.right)
      
  def find(self, key):
    x = self.root
    y = None
    z = Node(key)
    flag = False
    while x != None: 
      y = x
      if(z.key < y.key):
        x = x.left
      elif(y.key < z.key):
        x = x.right
      else:
        flag = True
        break
    return flag
    
  
n = int(input())
bst = BST()
for _ in range(n):
  query = input().split()
  if query[0] == "insert":
    bst.insert(int(query[1]))
  elif query[0] == "find":
    print("yes" if bst.find(int(query[1])) else "no")
  elif query[0] == "print":
    
    root = bst.root
    bst.inorder(root)
    print()
    bst.preorder(root)
    print()

Solution (Python):

"""
Created on Sat Mar  2 17:11:49 2019

@author: Yamazaki Kenichi
"""

m = int(input())
A = [list(input().split()) for i in range(m)]

T = [[-1,-1,-1,-1]]
def insert(T,u,x):
    if T[0][3] == -1:
        T[0][3] = x
        return
    if x < T[u][3]:
        if T[u][1] == -1:
            T[u][1] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][1],x)
    else:
        if T[u][2] == -1:
            T[u][2] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][2],x)
def ino(u):
    if T[u][1] != -1:
        ino(T[u][1])
    ino_res.append(str(T[u][3]))
    if T[u][2] != -1:
        ino(T[u][2])
def pre(u):
    pre_res.append(str(T[u][3]))
    if T[u][1] != -1:
        pre(T[u][1])
    if T[u][2] != -1:
        pre(T[u][2])
def find(u,x):
    if x == T[u][3]:
        return True
    elif x < T[u][3]:
        if T[u][1] == -1:
            return False
        return find(T[u][1],x)
    else:
        if T[u][2] == -1:
            return False
        return find(T[u][2],x)
for c in A:
    if c[0] == 'insert':
        insert(T,0,int(c[1]))
    elif c[0] == 'find':
        print('yes') if find(0,int(c[1])) else print('no')
    else:
        ino_res = []
        ino(0)
        pre_res = []
        pre(0)
        print(' '+' '.join(ino_res))
        print(' '+' '.join(pre_res))

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.inorder = []
        self.preorder = []

    def insert(self, node):

        p = None
        x = self.root        
        while x is not None:
            p = x
            
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        
        node.parent = p

        if p is None:
            self.root = node
        else:
            
            if node.key <= p.key:
                
                p.left = node
            else:
                
                p.right = node

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

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

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

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

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

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == 'insert':
        key = int(line[1])
        tree.insert(Node(key))
    elif line[0] == 'find':
        key = int(line[1])
        if tree.find(key):
            print('yes')
        else:
            print('no')

Solution (Python):
import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if 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 and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        print('yes' if x else 'no')
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    elif line[0] == 'f':
        tree.find(int(line.split()[1]))
    else:
        tree.print()

Solution (Python):
import sys

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

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, node):
        def helper(root):
            y, x = None, root
            while isinstance(x, TreeNode):
                y = x
                if node.val < x.val:
                    x = x.left
                else:
                    x = x.right
            if y is None:
                root = node
            elif node.val < y.val:
                y.left = node
            else:
                y.right = node
            return root
            
        self.root = helper(self.root)

    def find(self, val):
        def helper(root):
            if root is None:
                return None
            elif root.val == val:
                return root
            elif val < root.val:
                return helper(root.left)
            else:
                return helper(root.right)
        return helper(self.root)

    
    def inorder(self):
        def helper(root):
            return [] if root is None else helper(root.left) + [root.val] + helper(root.right)
        return helper(self.root)

    def preorder(self):
        def helper(root):
            return [] if root is None else [root.val] + helper(root.left) + helper(root.right)
        return helper(self.root)

if __name__ == '__main__':
    q = sys.stdin.readline()
    q = int(q)
    bst = BST()
    for _ in range(q):
        tmp = sys.stdin.readline()
        if tmp.startswith('print'):
            print ' ' + ' '.join(map(lambda x: str(x), bst.inorder()))
            print ' ' + ' '.join(map(lambda x: str(x), bst.preorder()))
        elif tmp.startswith('insert'):
            _, val = tmp.split()
            node = TreeNode(int(val))
            bst.insert(node)
        elif tmp.startswith('find'):
            _, val = tmp.split()
            print ('yes' if bst.find(int(val)) is not None else 'no')

Solution (Python):



import sys

class BinarySearchTree(object):
    def __init__(self):
        super(BinarySearchTree, self).__init__()
        self.root = None
        self.count = 0

    def insert(self, val):
        node = Node(val)
        y = None
        x = self.root
        while x != None:
            y = x
            if node.id_ < x.id_:
                x = x.left
            else:
                x = x.right
        node.parent = y

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

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

    def __str__(self):
        return 'Call to_inorder_walk() or to_preorder_walk()'

    def to_inorder_walk(self):
        return self._to_inorder_walk(self.root)

    def to_preorder_walk(self):
        return self._to_preorder_walk(self.root)

    def _to_inorder_walk(self, node):
        if node == None: return ''
        str_ = self._to_inorder_walk(node.left)
        str_ += ' %d' % (node.id_)
        str_ += self._to_inorder_walk(node.right)
        return str_

    def _to_preorder_walk(self, node):
        if node == None: return ''
        str_ = ' %d' % (node.id_)
        str_ += self._to_preorder_walk(node.left)
        str_ += self._to_preorder_walk(node.right)
        return str_

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

    def __str__(self):
        str_ = '%d' % (self.id_)
        return str_


bst = BinarySearchTree()

_nops = int(sys.stdin.readline())
for _ in range(0, _nops):
    op = sys.stdin.readline().rstrip().split(' ')
    if op[0] == 'insert':
        bst.insert(int(op[1]))
    elif op[0] == 'print':
        print bst.to_inorder_walk()
        print bst.to_preorder_walk()
    elif op[0] == 'find':
        if bst.find(int(op[1])):
            print 'yes'
        else:
            print 'no'
    else:
        pass

Solution (Python):
import sys


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

    def __str__(self):
        return "Not implemented yet."

    def __repr__(self):
        return self.__str__()


def insert(key, node):
    if key < node.key:
        if node.left is None:
            left_node = Node(key, node)
            node.left = left_node
        else:
            insert(key, node.left)
    else:
        if node.right is None:
            right_node = Node(key, node)
            node.right = right_node
        else:
            insert(key, node.right)


def find(key, node):
    if key == node.key:
        return True
    elif key < node.key:
        if node.left is None:
            return False
        else:
            return find(key, node.left)
    else:
        if node.right is None:
            return False
        else:
            return find(key, node.right)


def print_preorder(node):
    print(" %d" % node.key, end="")
    if node.left is not None:
        print_preorder(node.left)
    if node.right is not None:
        print_preorder(node.right)


def print_inorder(node):
    if node.left is not None:
        print_inorder(node.left)
    print(" %d" % node.key, end="")
    if node.right is not None:
        print_inorder(node.right)


def main():
    lines = sys.stdin.readlines()
    root = Node()

    for order in lines[1:]:
        if order.startswith("insert"):
            _, key = order.strip().split(" ")
            key = int(key)
            if root.key is None:
                root.key = key
            else:
                insert(key, root)
        elif order.startswith("find"):
            _, key = order.strip().split(" ")
            fild_result = "yes" if find(int(key), root) else "no"
            print(fild_result)
        elif order.startswith("print"):
            print_inorder(root)
            print("")
            print_preorder(root)
            print("")

if __name__ == "__main__":
    main()

Solution (Python):
from __future__ import print_function
from sys import stdin
class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None

def preorder_tree_walk(root):
    print('', root.id, end='')
    if root.left != None:
        preorder_tree_walk(root.left)
    if root.right != None:
        preorder_tree_walk(root.right)

def inorder_tree_walk(root):
    if root.left != None:
        inorder_tree_walk(root.left)
    print('', root.id, end='')
    if root.right != None:
        inorder_tree_walk(root.right)

def insert(root, z):
    y = None
    x = root
    while isinstance(x, Node):
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right
    z.parent = y

    if y == None:
        root = z
    elif z.id < y.id:
        y.left = z
    else:
        y.right = z
    return root

def find(root, x):
    while root != None and x != root.id:
        if x < root.id:
            root = root.left
        else:
            root = root.right
    return root


n = int(raw_input())
root = None
for i in xrange(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        num = int(cmd[7:])
        root = insert(root, Node(num))
    elif cmd.startswith('p'):
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()
    else:
        
        num = int(cmd[5:])
        if find(root, num) != None:
            print('yes')
        else:
            print('no')

Solution (Python):
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y
    if y == None:
        tree = z
    elif y['key'] > k:
        y['left'] = z
    else:
        y['right'] = z
    return tree

def find(tree,k):
    x = tree
    while x != None:
        if x['key'] == k:
            print "yes"
            return
        elif x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    print "no"

def middleorder(x):
    if x != None:
        middleorder(x['left'])
        print x['key'],
        middleorder(x['right'])

def preorder(x):
    if x != None:
        print x['key'],
        preorder(x['left'])
        preorder(x['right'])



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, int(c[7:]))
    elif c[0] == 'f':
        find(tree, int(c[5:]))
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Solution (Python):
class Tree:
    root = None

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

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

    def find(self, value):
        print('yes' if self.root.find(value) else 'no')

    def print(self):
        print(' ', end='')
        print(*self.root.print_in())
        print(' ', end='')
        print(*self.root.print_pre())


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

    def find(self, value):
        diff = self.key - value
        if diff == 0:
            return True
        elif diff > 0:
            return self.left and self.left.find(value)
        else:
            return self.right and self.right.find(value)

    def print_pre(self):
        yield self.key
        if self.left:
            for k in self.left.print_pre(): yield k
        if self.right:
            for k in self.right.print_pre(): yield k

    def print_in(self):
        if self.left:
            for k in self.left.print_in(): yield k
        yield self.key
        if self.right:
            for k in self.right.print_in(): yield k


tree = Tree()
m = int(input())

while m:
    l = input()
    f = l[0]
    if f == 'i':
        tree.insert(Node(int(l.split()[1])))
    elif f == 'f':
        tree.find(int(l.split()[1]))
    else:
        tree.print()
    m -= 1

Solution (Python):

from __future__ import division, print_function
from sys import stdin
   
   
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
   
   
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
   
def tree_find(top, k):
    x = top
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
   
   
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
   
   
n = int(stdin.readline())
   
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        
        top = tree_insert(top, Node(key))
    elif cmd.startswith('f'):
        key = int(cmd[5:])
        if tree_find(top, key) != None:
            print('yes')
        else:
            print('no')
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Solution (Python):
class BinarySearchTree:
    root = None
    def insert(self, k):
        y = None
        x = self.root
        z = Node(k)
        while x:
            y = x
            if z.k < x.k:
                x = x.l
            else:
                x = x.r
        z.p = y
         
        if y == None:
            self.root = z
        else:
            if z.k < y.k:
                y.l = z
            else:
                y.r = z
                
    def find(self, x, k):
        while x != None and k != x.k:
            if k < x.k:
                x = x.l
            else:
                x = x.r
        return x
         
    def preParse(self, u):
        if u == None:
            return
        print("", str(u.k), end = "")
        self.preParse(u.l)
        self.preParse(u.r)
 
    def inParse(self, u):
        if u == None:
            return
        self.inParse(u.l)
        print("", str(u.k), end = "")
        self.inParse(u.r)
 
class Node: 
    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None
 
if __name__ == '__main__':
    n = int(input().rstrip())
    x = BinarySearchTree()
    for i in range(n):
        com = input().rstrip()
        if com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("find"):
            k = int(com.split(" ")[1])
            if x.find(x.root, k) != None:
                print("yes")
            else:
                print("no")
        else:
            x.inParse(x.root)
            print()
            x.preParse(x.root)
            print()